퀵 정렬(Quick Sort)

Sorting 알고리즘 중 가장 효율적이고 빠른 방식.

이름 자체에서도 퀵이란 명칭이 붙을 정도로 가장 많이 사용되고 가장 잘 사용되는 방식이다.

1. 먼저 PIVOT 계수를 정한다. PIVOT 계수는 임의로 선정할 수 있으나, 중간 크기의 숫자를 PIVOT 계수로 선정하는 것이 가장 효율적이기 때문에 대부분 3개의 임의의 숫자를 랜덤으로 선택한 후 3개 중 가운데 값을 PIVOT 계수로 정한다.

2. PIVOT 값과 LEFT 값을 비교한다. 만약 LEFT 값이 PIVOT 값보다 크다면 PIVOT 값과 RIGHT 값을 비교한다.

RIGHT 값이 PIVOT 값보다 크다면, RIGHT 인덱스를 왼쪽으로 위치시킨 후 다시 PIVOT 값과 비교한다.

3. RIGHT 값이 PIVOT 값보다 작다면, LEFT 값과 RIGHT 값을 바꾼 후, LEFT 값을 오른쪽으로 한칸 전진시킨다.

4. LEFT 값과 RIGHT 값이 만날 때까지 2~3번 과정을 반복한다.

5. LEFT와 RIGHT가 만나면 해당 값과 PIVOT 값을 비교한다. PIVOT 값이 크면 오른 쪽 작으면 왼쪽에 위치 시킨다.

6. 3을 기준으로 블록을 크게 3보다 큰 값, 3보다 작은 값으로 나뉘게 된다. 3보다 작은 블록에 대해 다시 PIVOT 계수를 설정한다.

7. 기존에 한 방식대로 다시 LEFT와 RIGHT 값을 PIVOT과 비교한 후, 값을 교환한다.

8. 3보다 큰 블록에 대해서도 위와 같이 비교한다.

9. 최종 sorting이 완료된다.

퀵소트는 큰 배열을 정렬하기엔 좋은 방식이지만, 블록이 점점 줄어들면서 계속 퀵소트를 할 경우 불필요한 부하를 낳을 수 있다. 하여 어느 정로 블록이 줄어들면 삽입 정렬 등으로 정렬 방식을 변환하는 것이 좋다.

	void quickSort(int numbers[], int array_size);
	void q_sort(int numbers[], int left, int right);
	int main(int argc, char **argv)
	{
	const int itemSize = 6;
	int array[itemSize] = {3,8,0,2,1,4};
	quickSort(data, itemSize);
	}
	void quickSort(int numbers[], int array_size)
	{
	q_sort(numbers, 0, array_size -1);
	}
	void q_sort(int numbers[], int left, int right)
	{
	int pivot, l_hold, r_hold;
	l_hold = left;
	r_hold = right;
	pivot = numbers[left]; // 0번째 원소를 피봇으로 선택
	while (left < right)
	{
	// 값이 선택한 피봇과 같거나 크다면, 이동할 필요가 없다
	while ((numbers[right] >= pivot) && (left < right))
	right --;
	// 그렇지 않고 값이 피봇보다 작다면,
	// 피봇의 위치에 현재 값을 넣는다.
	if (left != right)
	{
	numbers[left] = numbers[right];
	}
	// 왼쪽부터 현재 위치까지 값을 읽어들이면서
	// 피봇보다 큰 값이 있다면, 값을 이동한다.
	while ((numbers[left] <= pivot) && (left < right))
	left ++;
	if (left != right)
	{
	numbers[right] = numbers[left];
	right --;
	}
	}
	// 모든 스캔이 끝났다면, 피봇값을 현재 위치에 입력한다.
	// 이제 피봇을 기준으로 왼쪽에는 피봇보다 작거나 같은 값만 남았다.
	numbers[left] = pivot;
	pivot = left;
	left = l_hold;
	right = r_hold;
	// 재귀호출을 수행한다.
	if (left < pivot)
	q_sort(numbers, left, pivot - 1);
	if (right > pivot)
	q_sort(numbers, pivot+1, right);
	}

view raw gistfile1.c hosted with ❤ by GitHub