[자료구조] 퀵소트

퀵소트는 가장 빠른 정렬 알고리즘이다.

시간복잡도 - 빅오는 평균 O(NlogN)이며 최악은 O(N^2)이다.

최악일 때는 배열이 정렬되어 있을 때이다.

구성 - 

필요한 것 - left, right, low, high, pivot

배열 a

[0] [1] [2] [3] [4] [5] [6]

 3    2   6   5   4   1   7

left - 가장 왼쪽 가리킴 (고정) - 인덱스 0

right - 가장 오른쪽 가리킴 (고정) - 인덱스 6

low - 왼쪽+1 가리킴 (이동) - 인덱스 1

high - 가장 오른쪽 가리킴 (이동) - 인덱스 6

pivot - 정렬의 기준을 잡을 값 (가장 왼쪽을 잡을 때: 3)

실행순서

 

처음 실행시 3 2 6 5 4 1 7

1. low가 오른쪽으로 이동하며 피벗(3)보다 큰 값을 찾는다. - 찾은것은 인덱스 2의 6이다.

2. high가 왼쪽으로 이동하며 피벗(3)보다 작은 값을 찾는다. - 찾은것은 인덱스 5의 1이다.

3. low와 high의 값을 서로 바꿔준다. 3 2 [1] 5 4 [6] 7이 된다.

3 2 [1] [5] 4 6 7 이때 low는 5를 잡았고 high는 1을 잡았다.

하지만 low와 high는 교차했으므로 바꾸지 않고 while문을 벗어난다.

4. 마지막은 피벗과 high의 값을 바꿔준다. 

피벗은 3이고 high값은 1이다. 

[3] 2 [1] 5 4 6 7 -> [1] 2 [3] 5 4 6 7이 된다.

5. 그 다음은 방금 이동한 피벗값은 고정하고 양쪽에 퀵소트를 실행한다.

1 2 [3] 5 4 6 7

왼쪽은 피벗값이 1이고 low가 2 high가 2이다.

오른쪽은 피벗값이 5이고 low가 4 high가 7이다.

6. 반복하여 정렬한다.

#include <stdio.h>

void swap(int arr[], int a, int b){  // low와 high 또는 left와 high의 값을 바꿔준다.

int temp = arr[a];

arr[a] = arr[b];

arr[b] = temp;

}

int partition(int arr[], int left, int right){

int pivot = arr[left];  // 피벗은 가장 왼쪽 값

int low = left+1;  // low는 피벗보다 1큰 인덱스

int high = right;  // right는 가장 오른쪽 인덱스

while(low <= high){  // 단순히 아래 if문 탈출할때 탈출문

while(pivot > arr[low]){  // 3보다 큰 수가 아니라면 low 인덱스 증가 (=> 아닌 이유는 자기자신일때 멈춤)

low++;

}

while(pivot < arr[high]){  // 3보다 작은 수가 아니라면 high 인덱스 감소

high--;

}

if(low <= high){  // 교차하기 전까진 low와 high를 서로 바꿔줘야한다

swap(arr, low, high);  // low와 high의 값을 교환한다.

}

}

swap(arr, left, high);  // low와 high값을 모두 교환한 후에 피벗값과 high값을 교환한다.

return high;   // high를 반환하는 이유는 교차된 마지막 high의 인덱스가 기준을 잡아주게 된다.

}

void quick(int arr[], int left, int right){ 

if(left <= right){  // 바꿀 것이 없을 때 걸러줌 (예를 들어 왼쪽에 2개 남은 경우 (0,0) 또는 1개 남으면 (0, -1) 될때 걸러줌)

int pivot = partition(arr, left, right);  // 고정할 값을 구한다.

quick(arr, left, pivot-1);  // 고정된 값의 왼쪽에 퀵소트

quick(arr, pivot+1, right);  // 고정된 값의 오른쪽에 퀵소트

}

}

int main(){

int arr[] = {3,2,6,5,4,1,7};  // 임의의 수를 입력함

int len = sizeof(arr)/sizeof(int);  // 전체 길이 7

int i;

quick(arr, 0, len-1);  // 배열, 배열의 첫번째 인덱스, 배열의 마지막 인덱스 넘겨줌

 

for(i=0; i<len; i++){  // 출력

printf("%d ", arr[i]);

}

printf("\n");

return 0;

}