퀵정렬 복습

오늘은 퀵정렬에 대해 배워보았습니다. 말에서 부터 뭔가 굉장히 빠를 거 같은 느낌이 들죠?

선택,삽입,버블 정렬은 다 O(N^2) 복잡도의 알고리즘이었는데요 . 퀵정렬은 무려 O(n log n)의 복잡도를 가지고 있습니다. 

 

log n 은 어마어마한 수인데요 생각해보면 n = 1000 log n = 10 정도고 n = 1000000 이면 n은 20 정도 입니다. 실제로 알고리즘을 조금 더 공부하면 log n의 대단함을 더 느낄 수 있다고 하네요. 

 

이런 퀵정렬의 핵심은 "특정한 값을 기준으로 큰 숫자와 작은 숫자를 나누면 어떨까!" 입니다. 

이 특정한 값을 보통 기준 pivot 값이라고 칭합니다. 

 

퀵정렬은 큰 문제를 나눠서 해결하는 분할 정복 알고리즘에 기반하기 때문에 더 빠르게 정렬이 가능합니다. 

-> 특정한 값을 기준으로 큰 숫자와 작은 숫자를 비교하고 교환 후 배열을 반으로 나눠 또 알고리즘을 진행합니다. 

 

예시를 들어보겠습니다. 

 

3 5 8 2 9 1 4 6 7 

 

다음 배열을 이용해서 정렬을 진행해보겠습니다. 보통 기준 값은 가장 앞 수가 됩니다. 이 수를 기준으로 왼쪽과 오른쪽으로 부터 다가갑니다. 왼쪽은 기준 값보다 큰 값, 오른쪽은 기준 값보다 작은 값을 찾습니다.

 

3 5 8 2 9 1 4 6 7 

 

3보다 큰 수는 5로 결정되고, 오른쪽에서는 3보다 작은 수 1로 결정되었습니다. 이 수를 교환해줍니다. 

 

3 1 8 2 9 5 4 6 7 

 

3보다 큰 수는 8이고 3보다 작은 수는 2 입니다. 이 수를 교환해줍니다. 

 

3 1 2 8 9 5 4 6 7

 

3보다 큰 수는 8이고 3보다 작은 수는 2입니다. 여기서 엇갈렸습니다! 그럼 작은 값과 기준 값은 교환해줍니다! 

 

2 1 3 8 9 5 4 6 7

 

여기서 보면 3의 왼쪽은 3보다 작고 3의 오른쪽은 3보다 크다는 특징이 있습니다. 그리고 이게 3을 기준으로 두 그룹으로 분할이 됩니다. 이 두개에서 다시 퀵정렬을 수행해주면 되는 겁니다. 

 

2 1 3 8 9 5 4 6 7

제일 앞에 있는게 또 기준이 됩니다. 앞쪽 그룹에서 어떤 일이 일어나는지 먼저 살펴보겠습니다. 2을 기준으로 큰 값을 찾습니다. 없네요. 작은 값은 1이 있습니다. 그럼 엇갈렸기 때문에 기준 값 2와 1을 바꿔줍니다. 

 

1 2 3 8 9 5 4 6 7

 

그럼 1과 쪼개집니다. 1은 이제 하나니깐 정렬을 더 이상 진행하지 않습니다. 뒤에 그룹을 한 번 볼까요? 

 

1 2 3 8 9 5 4 6 7

 

기준 8보다 큰 값을 왼쪽부터 찾아줍니다. 9입니다. 작은 값을 오른쪽 부터 찾아줍니다. 7입니다.

 

1 2 3 8 9 5 4 6 7

 

엇갈리지 않으니깐 바꿔줍니다. 

 

1 2 3 8 7 5 4 6 9

 

다시 8보다 큰거를 찾아줍니다. 9입니다. 8보다 작은 거를 찾아줍니다. 6입니다. 엇갈렸습니다. 

그럼 작은 값과 기준 값을 바꿔줍니다. 

 

1 2 3 6 7 5 4 8 9

 

보면 8의 왼쪽에는 8보다 작은 값이 없습니다. 또 8의 오른쪽엔 8보다 큰 값 밖에 없습니다. 또 이 두 그룹을 퀵정렬 해줍니다. 앞쪽을 먼저 보겠습니다. (사실 9는 하나이기 때문에 신경 안 써줘도 됩니다.)

 

1 2 3 6 7 5 4 8 9

 

기준이 6보다 큰 값은 7 작은 값은 4 입니다. 엇갈리지 않았으니 바꿔줍니다. 

 

1 2 3 6 4 5 7 8 9

 

기준 6보다 큰 값은 7 작은 값은 오른쪽에서부터 진행하니깐 5입니다. 엇갈렸습니다.

5와 6을 바꿔줍니다. 

 

1 2 3 5 4 6 7 8 9

 

그럼 또 두 그룹으로 나눠서 퀵정렬을 해줍니다. 앞의 그룹먼저 보겠습니다. 

 

1 2 3 5 4 6 7 8 9 

 

5를 기준으로 찾습니다. 큰 값을 찾지 못했습니다. 작은 값은 4입니다. 엇갈렸음으로 4와 5를 바꿔줍니다. 

 

1 2 3 4 5 6 7 8 9 

 

4도 7도 원소가 하나입니다. 

 

1 2 3 4 5 6 7 8 9

 

이렇게 퀵 정렬이 끝났습니다!

 

 

 

구현은 C로 하였습니다. 

#include <stdio.h>

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

void quickSort(int *data, int start, int end){//start 정렬을 수행하는 부분집합의 첫번째, end는 마지막 
	if(start >= end){ // 원소가 1개인 경우
	 return; 
	}
	int key = start; //키는 첫번째 원소
	int i = start +1;// 왼쪽부터 하나씩 확인하는 인덱스
	int j = end; // 마지막 값부터 작은 걸 찾음
	int temp;//Swap 을 위한 변수
	while(i <= j){ // 엇갈릴 때까지 반복 
		while(data[i]<=data[key]&i<=end){
			i++;// i보다 큰 값을 만날 때까지 이동 
		} 
		while(data[j]>=data[key]&&j>start) {//키 값보다 작은 값 값이 넘억 
			j--;
		}
		if(i > j){//엇갈림 
			temp = data[j];
			data[j]	= data[key];
			data[key] = temp;		
		}else{//안 엇갈림 
			temp = data[j];
			data[j] = data[i];
			data[i] = temp; 
		}
	} 
	quickSort(data,start,j - 1);
	quickSort(data,j + 1,end);
}
int main(void){
	quickSort(data,0,number-1);
	int i;
	for(i = 0;i <number; i++)
		printf("%d ",data[i]);
}