퀵 정렬(Quick Sort)

퀵 정렬은 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 정렬 알고리즘이다.

일반적으로 많이 사용되는 정렬 알고리즘이며 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이다.

기본적은 퀵 정렬은 *첫 데이터를 기준 데이터(Pivot)*으로 설정한다.

C++ 구현 코드는 다음과 같다.

#include <iostream>
#include <random>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> getRandomArray(const int randomNumberCount)
{
	int temp, x, y;
	random_device rd;
	mt19937 gen(rd());

	uniform_int_distribution<int> dis(0, randomNumberCount - 1);

	vector<int> randomArray(randomNumberCount);
	
	for (int i = 0; i < randomNumberCount; i++)
	{
		randomArray[i] = i + 1;
	}

	for (int i = 0; i < randomNumberCount; i++)
	{
		x = dis(gen);
		y = dis(gen);
		if (x != y)
		{
			temp = randomArray[x];
			randomArray[x] = randomArray[y];
			randomArray[y] = temp;
		}
	}

	return randomArray;
}

int exchangeValue(vector<int>* exchangeArray, int xIndex, int yIndex) {
	int temp = (*exchangeArray)[xIndex];
	(*exchangeArray)[xIndex] = (*exchangeArray)[yIndex];
	(*exchangeArray)[yIndex] = temp;
	
	return 0;
}

int quickSort(vector<int>* rArray, int first, int last) {
	if (first >= last) {
		return 0;
	}
	int pivot = (*rArray)[first];
	int pivotIndex = first;
	int leftPartionIndex = first + 1;
	int rightPartionIndex = last;
	
	while (leftPartionIndex <= rightPartionIndex) {
		while ((leftPartionIndex <= last) && ((*rArray)[leftPartionIndex] <= pivot)) {
			leftPartionIndex++;
		}
		while ((rightPartionIndex > first) && ((*rArray)[rightPartionIndex] >= pivot)) {
			rightPartionIndex--;
		}

		if (leftPartionIndex <= rightPartionIndex) {
			exchangeValue(rArray, leftPartionIndex, rightPartionIndex);
		} else {
			exchangeValue(rArray, rightPartionIndex, pivotIndex);
		}
	}
	quickSort(rArray, first, rightPartionIndex - 1);
	quickSort(rArray, rightPartionIndex + 1, last);

	return 0;
}


int main(void) 
{
	const int randNumberLength = 100;
	vector<int> randArray = getRandomArray(randNumberLength);

	quickSort(&randArray, 0, randNumberLength - 1);

	for (int i = 0; i < randArray.size(); i++) {
		cout << randArray[i] << endl;
	}

	return 0;
}