[자료구조] 퀵정렬 Quick Sort

안녕하세요 주인장 H입니다. 

오늘은 퀵정렬에 대해 알아보겠습니다.

지금까지 배운 정렬은 시간복잡도 O(N^2)를 가진 알고리즘 이였습니다. 처리할 데이터가 많다면

사용하기에 부담이 되겠지요. 그렇기에 대표적인 빠른 알고리즘이 바로 퀵정렬입니다. 

퀵정렬은 대표적인 분할 정복 알고리즘으로서 평균속도가 O(N*log N)입니다. 

 

1~10까지의 무질서한 숫자를 오름차순으로 정리한다고 할때, 

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

특정한 값(피벗pivot)을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눕니다.

 

예를들어 (1) 10 5 8 7 6 4 3 2 9 라는 숫자가 있다고 가정합니다.

이 경우 1보다 큰 숫자를 왼쪽에서, 1보다 큰 숫자를 오른쪽에서 찾습니다. 

1보다 작은 숫자는 차지 못해서 1까지 도달합니다. 이때 작은 값의 인덱스가 큰 값의 인덱스보다 작으므로 

피벗 값과 작은 값의 위치를 바꿉니다. 즉, 1과 1을 서로 교환합니다. 

 

3 7 8 1 5 9 6 10 2 4 

 

3을 피벗값으로 설정한다면

왼쪽에서 오른쪽으로 큰값, 오른쪽에서 왼쪽으로 갈때 작은값을 찾습니다. 

그렇게 되면 7 과 2가 선택되는데 두 값을 변경해줍니다.

 

3 2 8 1 5 9 6 10 7 4 

 

피벗값은 동일하구요. 다시 진행을 하면 3보다 큰 값 8, 작은값 1을 찾습니다. 

 

3 2 1 8 5 9 6 10 7 4 

 

이번엔 큰 값이 8, 작은 값이 1. 인덱스가 서로 엇갈립니다. 이럴땐 작은값과 피벗값을 서로 교환해줍니다. 

 

1 2 3 8 5 9 6 10 7 4 

 

이렇게 되면 3을 기준으로 왼쪽과 오른쪽 그룹으로 나누어 진행합니다. 

왼쪽에서 큰값, 오른쪽에서 작은값을 찾습니다. 이때 엇갈리기 때문에 1과 1을 교환해줍니다. 

 

1 2 3 8 5 9 6 10 7 4 

 

이제 2는 데이터가 1개이기 때문에 아래와 같이 1 2 3 이 정렬되었습니다. 

 

1 2 3 8 5 9 6 10 7 4 

이제 오른쪽도 8을 피벗으로 하여 다시 퀵정렬을 진행하는데요 

8보다 큰값 9, 작은값 4 인덱스가 안겹치니 서로 바꿔 줍니다. 

 

1 2 3 8 5 4 6 10 7 9

 

8보다 큰 값 10, 작은값 7. 서로 바꿔줍니다. 인덱스가 겹치지 않으니 피벗은 그대로입니다. 

 

1 2 3 8 5 4 6 7 10 9

 

이제 큰값 10, 작은값 7 인덱스가 겹치니 8과 7을 교환 해줍니다. 

 

1 2 3 7 5 4 6 8 10 9

 

이제 다시 8을 기준으로 왼쪽 그룹과 오른쪽 그룹을 진행하면 됩니다. 

7 5 4 6 그룹을 진행하면  7보다 큰값을 찾지 못했기 때문에 끝까지 가고,

오른쪽에선 6, 인덱스가 겹치니 작은값과 피벗값을 교환해준다. 

 

1 2 3 6 5 4 7 8 10 9

 

6을 기준으로 오른쪽으로 큰값이 없다. 왼쪽으론 4가 선택 그럼 6과 4를 서로 변경해주면,

 

1 2 3 4 5 6 7 8 10 9

 

이후엔 설명을 생략하고 계속 진행하겠습니다. 

 

1 2 3 4 5 6 7 8 10 9

1 2 3 4 5 6 7 8 9 10

1 2 3 4 5 6 7 8 9 10

 

하지만 퀵정렬이 언제나 빠를가요?

퀵 정렬의 시간 복잡도는 두 그룹으로 나누어 진행하기 때문에 O(N*log N)입니다. 하지만

최악의 경우, 이미 정렬이 거의 다 되어 있는 경우 시간 복잡도는 O(N^2)에 가깝습니다. 

 

 

#include <stdio.h>
int data[] = { 4,10,5,3,2,9,7,8,6,1 };
int number = 10; 

quickSort(int* data, int start, int end) {
	if (start >= end) {
		return;
	}

	int key = start; //key는 첫 번째 원소
	int i = start + 1; 
	int j = end;
	int temp;

	while (i <= j) { //엇갈릴때 까지 반복
		//키값보다 큰 값을 만날 때
		while (i <= end && data[i] <= data[key]) {
			i++;
		}
		while (data[j] >= data[key]) {
			j--;
		}
		//현재 엇갈린 상태면 키 값과 교체
		if (i > j) {
			temp = data[j];
			data[j] = data[key];
			data[key] = temp;
		}
		//엇갈리지 않았다면 i와 j를 교체
		else {
			temp = data[i];
			data[i] = data[j];
			data[j] = temp;
		}
	}

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


int main(void) {
	quickSort(data, 0, number - 1);
	for (int i = 0; i < number; i++) {
		printf("%d", data[i]);
	}
	return 0;
}