[알고리즘] 퀵 정렬 (Quick Sort)

1. 퀵 정렬(Quick Sort)이란?

Pivot(축) 값을 기준으로 연속적으로 분할하며 정렬하는 기법으로 pivot 값을 중심으로 pivot보다 작은 값은 왼쪽으로, pivot보다 큰 값은 오른쪽에 배열시키며 정렬이 완료될 때까지 반복적으로 수행한다.

 

2. 알고리즘

 1) 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.

 2) 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다

 3) 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.

 

3. 퀵 정렬(Quick Sort) 예제

배열에 9, 5, 7, 3, 1, 8, 4가 들어 있다고 가정하고 정렬해 보자.

 

1. Sort 구간의 가장 우측의 값을 pivot으로 설정

 

2. 한 구간 안에서 다음을 반복 수행

 1) 구간 좌측부터 pivot보다 큰 값을 i를 증가 시키면서 검사

 2) 구간 우측부터 pivot보다 작은 값을 j를 감소 시키면서 검사

 3) i<j이면 i의 자리에 있는 값과 j으 ㅣ자리에 있는 값을 swap

 

3. i == j이거나 i > j이면 한 구간에 대한 교환이 완료된 것으로 i의 자리에 있는 값과 pivot 값을 swap

(이때 pivot 값을 중심으로 좌측에는 pivot보다 작은 값이, 우측에는 pivot보다 큰 값들이 위치)

 

4. 이러한 분할 과정을 pivot 값을 중심으로 나누어 좌측과 우측 두 구간에 대하여 똑같이 반복. (구간의 크기가 1이 될 때까지 재귀 호출)

 

 

4. 소스코드와 결과

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

void quickSort(int* ary, int size);
void output(int* ary, int size);
void initArray(int* ary, int n);

int main()
{
	int dataList[10000];


	int startTime, endTime;
	int size = sizeof(dataList) / sizeof(dataList[0]);

	srand((unsigned int)time(NULL));

	initArray(dataList, size);

	
	quickSort(dataList, size); 	/* 퀵 정렬 함수 호출 */
	output(dataList, size);
	
	getchar();
	return 0;
}

void quickSort(int* ary, int size)
{
	int pivot, temp;
	int i, j;

	if (size <= 1) return; // 구간값이 1이하이면 sort가 완료된 것 이므로 return

	pivot = ary[size - 1];

	i = -1;
	j = size - 1;

	while (1) {
		while (ary[++i] < pivot);
		while (j>0 && ary[--j] > pivot);
		if (i >= j)
			break;

		temp = ary[i];
		ary[i] = ary[j];
		ary[j] = temp;

	}

	temp = ary[i];
	ary[i] = ary[size -1];
	ary[size -1] = temp;

	quickSort(ary, i); 	// 좌측 소구간에 대한 퀵 정렬 재귀 호출
	quickSort(ary + i + 1, size - i - 1); // 우측 소구간에 대한 퀵 정렬 재귀 호출
	
}


void output(int* ary, int size)
{
	for (int i = 0; i < size; i++)
	{
		printf(" %d ", ary[i]);
	}
	printf("\n");
}


void initArray(int* ary, int n)
{
	int i;
	for (i = 0; i < n; ++i)
		ary[i] = rand() % 1000 + 1;
}

 

결과