[자료구조] [C] 퀵 정렬 (quick sort)

퀵정렬(위키백과)

퀵정렬

요약)
피벗을 정한다. 피벗보다 작은 거 왼쪽으로 큰 거 오른쪽으로 보냄 (정렬 안되어있음) 피벗은, 중간값을 잡는 등 응용을 할 수 있음.

과정)
피벗 가장 왼쪽 숫자라고 가정한다.
두개의 변수 low와 high를 사용한다.

low 변수는 피벗보다 작으면 통과하고, 크면 정지한다.
high 변수는 피벗보다 크면 통과하고, 작으면 정지한다.

정지된 위치의 숫자를 low와 high 교환한다.

쭉 가다가 low와 high가 교차되면 종료.

high 자리에 피벗(가장 왼쪽 숫자) 집어넣음.


   5    3    8    4    9    1    6    2    7   
피벗  low                                   high
             low                        high    

   5    3    2    4    9    1    6    8     7
             low                        high
                   low             high
                         low high

   5    3    2    4    1    9    6    8     7
                         low high
                         high low                 -stop
  
   1    3    2    4    5    9    6    8    7

즉 쉽게 설명하면,

정해논 규칙에 따라 피벗을 잡는다.

먼저! low 부터 오른쪽으로 이동함 그러다가 피벗보다 큰 순간 멈춤
그리고 high를 왼쪽으로 이동함 그러다가 피벗보다 작은 순간 멈춤

딱 그때 low와 high인덱스의 값을 바꿈

다시 low 오른쪽으로 이동 피벗보다 큰 순간 멈춤
high 왼쪽으로 이동 피벗보다 작은 순간 멈춤

딱 그때 low와 high 인덱스의 값을 바꿈

그러다가 high가 low보다 작아지면 high 인덱스의 값과 피벗 인덱스 값 바꿈.

이 함수를 순환호출한다.

 

#include <stdio.h>


void SWAP(int *a, int *b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}

int partition(int list[], int left, int right) {
	int pivot;
	int low, high;

	low = left;
	high = right + 1;
	pivot = list[left];
	do {

		do
			low++;
		while (low <= right && list[low] < pivot);
		do
			high--;
		while (high >= left && list[high] > pivot);
		if (low < high) SWAP(&list[low], &list[high]);

		for (int i = 0; i < 10; i++)
			printf("%d ", list[i]);

		printf("\n피벗: %d \n", pivot);


	} while (low < high);

	SWAP(&list[left], &list[high]);
	return high;
}

void quick_sort(int list[], int left, int right) {
	if (left < right) {
		int q = partition(list, left, right);
		quick_sort(list, left, q - 1);
		quick_sort(list, q + 1, right);
	}
}

int main(void) {
	int arr[10] = { 12,10,5,11,2,7,13,8,300,0 };
	printf("\n----정렬전---\n");
	for (int i = 0; i<10; i++)
		printf("%d ", arr[i]);

	printf("\n");

	printf("<정렬 과정>\n");
	quick_sort(arr, 0, 9);

	printf("\n----정렬후---\n");
	for (int i = 0; i < 10; i++)
		printf("%d ", arr[i]);
	printf("\n");

	return 0;
}