퀵 정렬 (Quick Sort)

1. 퀵 정렬

▶ 분할정복 알고리즘

input 배열을 반복적으로 분할해서 계산하는 알고리즘이며,  평균 시간복잡도가 O(N*logN) 

특정한 값 a을 기준으로 a보다 큰 수, a보다 작은 수를 나누자 !

 

※ 특정한 값 a = pivot

※ 일반적으로 첫번째 원소를 pivot 값으로 설정한다.

 

 

 

2. 퀵 정렬 예제

ex )  3  7  8  1  5  9  6  10  2  4  오름차순 정리하시오.

 

#include <stdio.h>

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

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

void quickSort(int* a, int start, int end) {
	int temp;
	if (start >= end) {        // 원소가 1개인 경우
		return;
	}
	
	int key = start;        // key = pivot = 1st 원소
	int i = start + 1;      // (왼쪽 출발 지점 index) 탐색 시작하는 key 바로 다음 원소 index 
	int j = end;            // (오른쪽 출발 지점 index)

	while (i <= j) {   //  #엇갈릴 때까지 반복 

		// [왼쪽 출발] : key 값보다 큰 값을 만날 때까지 오른쪽으로 이동
		while (a[i] <= a[key]) {                 
			i++;
		}

		// [오른쪽 출발] : key 값보다 작은 값을 만날 때까지 왼쪽으로 이동
		while (a[j] >= a[key] && j > start) {    
			j--;
		}

		if (i > j) {  // 엇갈리게 된 상태라면 key값과 작은 값 a[j] 교체 후 #while문 빠져나옴
			temp = a[j];
			a[j] = a[key];
			a[key] = temp;
		}

		else {        // 엇갈리지 않았다면 a[i]와 a[j] 위치 change 후 #while문 반복
			temp = a[i];
			a[i] = a[j];
			a[j] = temp;
		}

	}  

	quickSort(a, start, j - 1);
	quickSort(a, j + 1, end);
}

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

	return 0;
}

 

 

 

3. 퀵 정렬의 시간 복잡도

1 2 3 4 5 6 7 8 9 10 을 정렬하려 할 때,

 

▷▷ 선택정렬 등 :  N ^ 2 = 10 * 10 = 100

▶▶ 퀵정렬 :  1 2 3 4 5   /   6 7 8 9 10 으로 나누어서 정렬

                     2 * (5 * 5) = 2 * 25 = 50

 

∴  input이 N개일 때, 퀵 정렬의 시간복잡도는 O(N * logN)