[알고리즘] 퀵 정렬_구현

퀵 정렬 : 하나의 큰 문제를 두 개의 작은 문제로 분할하는 식으로 빠르게 정렬

#include<stdio.h>

int num = 10;
int data[10] = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 };

int main(void) {
	quickSort(data, 0, num - 1);

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

void quickSort(int *data, int st, int ed) {

	if (st >= ed) return;    // st > ed : 값이 원래 자리에 들어간 경우 
							 // ( ex_ 정렬된 값 1  2  3  5  6  7  8  9  10  1은 이미 정렬이 되어있다.  	
	int key = st;			 //       그러므로 quickSort(data, st, left - 1); : 0 -1이 나옴)
	int right = st + 1;      // st = ed : 값을 반으로 나누거나 전체에서 남은 원소가 1개
	int left = ed;			 // ( ex_ 정렬된 값 1  2  3  5  6  7  8  9  10  1에서 6을 기준으로 나눴을 때
	int tmp;                 //       1  2  3 까지 정렬이 완료되고 
							 //       quickSort(data, left + 1, ed); : left + 1 : 3, ed : 3인 경우
	while (right <= left) {

		while (data[key] >= data[right] && right <= ed) right++;

		while (data[key] <= data[left] && left > st) left--;

		if (right > left) {

			tmp = data[key];
			data[key] = data[left];
			data[left] = tmp;
		}
		else {
			tmp = data[right];
			data[right] = data[left];
			data[left] = tmp;
		}
	}

	printf("%d %d\n", st, left - 1);

	printf("%d %d\n", left + 1, ed);


	quickSort(data, st, left - 1);		
	quickSort(data, left + 1, ed);
//	반으로 쪼갤 때 left를 기준으로 왼쪽은 left보다 작은값들 오른쪽은 left보다 큰 값들만 정렬되어 있다.
}

위 코드에서 start 부분과 end 부분이 엇갈릴 경우 ( i >= j)

반복을 종료하고 자기 자신을 다시 호출하여 j 값을 기준으로 좌우로 나눠서 연산을 한다.

= > 즉, 함수가 자기 자신을 호출하는 재귀적 함수를 이용하여 퀵정렬을 구현할 수 있다.

​

위 코드를 코드만 봤을 때는 이해하기 어려울 수 있다. 위 코드를 풀어보면

// 1 10 5 8 7 6 4 3 2 9

​

1 10 5 8 7 6 4 3 2 9

1 10 5 8 7 6 4 3 2 9 i 1 j 0 // 0 -1 1 9

1 10 5 8 7 6 4 3 2 9 i 10 j 9 // 1 8 10 9

1 9 5 8 7 6 4 3 2 10 i 9 j 8 // 1 7 9 8

1 2 5 8 7 6 4 3 9 10 i 2 j 1 // 1 0 2 7

1 2 5 3 7 6 4 8 9 10 i 3 j 7

1 2 5 3 4 6 7 8 9 10 i 4 j 6

1 2 3 5 4 6 7 8 9 10 i 5 j 4

....

1 2 3 4 5 6 7 8 9 10 처럼 정렬이 된다.

여기서 0 -1, 10 9, 9 8, 1 0 는

if (start >= end) { // 원소가 1개인 경우 return; }

이것에 의해서 return이 되어 함수가 종료된다.

​

​

이렇게 기본적으로 퀵 정렬 알고리즘은 N번씩 탐색하되 반으로 쪼개 들어간다는 점에서 log N을 곱한

퀵 정렬의 평균 시간 복잡도

O(N * log2N)

을 가지고 있지만 최악의 시간 복잡도는 바로 N * N 즉 N ^ 2이다.

퀵 정렬의 최악 시간 복잡도

O(N ^ 2)

흔한 상황에서는 왠만하면 N * log N의 시간 복잡도를 가지지만

1 2 3 4 5 6 7 8 9 10 을 오름차순으로 정렬하는 경우 이미 정렬이 되어있기 때문에 시간 복잡도는 O( N ^ 2)에 가깝다.

↑ 위와 같은 경우 삽입 정렬의 경우 매우 빠르게 풀수 있습니다.

​

즉, 정렬할 데이터의 특성에 따라 적절한 정렬 알고리즘을 사용하는 것이 매우 중요하다.

​

퀵 정렬의 비교 횟수와 이동 횟수

퀵 정렬의 비교 횟수는 최악을 제외한 평균 O(N logN)이고

이동 횟수의 경우에도 약간의 예외를 두는데 최악은 마찬가지로 O(N ^ 2)이다.

하지만 평균적으로 제일 효율이 좋은 것으로 알려져 있기 때문에 평균 O(N logN)의 이동 횟수를 가진다.