퀵 정렬의 시간복잡도와 작동원리

퀵 정렬의 시간복잡도와 작동원리

퀵 정렬은 이름 그대로 빠른 알고리즘이다. 

시간복잡도가 O(N * logN)이다.

 

• 2 ^ 10 = 1,000
• 2 ^ 20 = 1,000,000
• log2N -> N이 1,000,000 일 때? 20

3 7 8 1 5 9 6 10 2 4  -> 3을 기준으로 오른쪽을 봤을 때 3보다 큰값(7)과 왼쪽을 봤을 때 3보다 작은 값(2)를 바꾼다.

3 2 8 1 5 9 6 10 7 4  -> 다시 오른쪽과 왼쪽을 보면서 큰값과, 작은 값을 찾아 바꾼다.

3 2 1 8 5 9 6 10 7 4  -> 이번에 서로 엇갈렸다(작은 값의 인덱스가 큰 값의 인덱스보다 더 작을 때). 이럴때는 작은 값과 3을 바꾼다.

1 2 3 8 5 9 6 10 7 4  -> 3보다 왼쪽에 있는 값은 3보다 작다. 3의 오른쪽에 있는 값들은 3보다 크다. 즉, 한 번 왼쪽과 오른쪽을 분할한 것이다. 3은 정렬이 이루어진 것이다. 

1 2 3 8 5 9 6 10 7 4  -> 왼쪽은 1이 피벗(기준값)이 된다. 오른쪽은 8이 피벗값이다. 왼쪽과 오른쪽에서 각각 큰값과 작은 값을 찾는다. 1을 기준으로 오른쪽으로 큰값은 2이고 오른쪽으로 작은값은 없으므로 자기자신을 선택한다. 이 경우는 아까와 같이 엇갈린 상태이므로 1과 자기자신을 바꾼다.

1 2 3 8 5 9 6 10 7 4  -> 2를 기준으로 피벗을 수행한다. 이 경우는 데이터가 한 개 이기 때문에 그대로 둔다.

1 2 3 8 5 9 6 10 7 4  -> 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  -> 8을 기준으로 피벗을 수행한다. 이 번에는 엇갈렸기 때문에 8과 7을 바꾼다.

1 2 3 7 5 4 6 8 10 9  -> 8을 기준으로 작은값은 왼쪽 큰 값은 오른쪽에 있다. 7과 10이 피벗이 된다. 7을 피벗하면 큰값은 없고 작은 값은 6이다. 이 경우에도 엇갈렸기 때문에 7과 6을 바꾼다.

1 2 3 6 5 4 7 8 10 9  -> 7을 기준으로 왼쪽은 작은 값이 있다.

....

1 2 3 4 5 6 7 8 9 10

 

 

1 2 3 4 5 6 7 8 9 10

기존 선택정렬, 버블정렬들의 시간복잡도는 아래와 같다.

N ^ 2 = 10 * 10 = 100

 

아래는 분할정복을 사용하는 퀵 정렬이다.

1 2 3 4 5 => 5 * 5 = 25

6 7 8 9 10 => 5 * 5 = 25

 

25 + 25 = 50

 

퀵 정렬은 분할정복을 사용하여 잘게 쪼갠 다음 그 것들을 각자 정렬하고 나중에 합치게 된다. 

 

시간복잡도 O(N * logN)에서 반으로 나누는 것은 logN이다. 데이터 개수는 N이다.

 

#include <stdio.h>

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

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

void quickSort(int *data, int start, int end){
if (start >= end){ //원소가 1개인 경우 종료시키기 
return;
}

int key = start;   //키는 첫번째 원소 => 1
int i = start + 1; //왼쪽부터 큰값을 찾을 때 인덱스(키값의 왼쪽) => 10
int j = end; //오른쪽에서 부터 인덱스 => 9
int temp;

while(i <= j){//엇갈리지 않을때 까지  반복. 
          //배열의 범위를 넘어가지않도록 하는 조건. 
while(i <= end && data[i] <= data[key]){ //키 값보다 큰 값을 만날때까지 반복. 
i++; 
}  
      // 범위를 넘어가지 않도록 하는 조건. 
while(j > start && data[j] >= data[key] ){ //키 값보다 작은 값을 만날때까지 반복.  
j--;
}

if(i > j){// 현재 엇갈린 상태면 키 값과 교체 
temp = data[j];
data[j] = data[key];
data[key] = temp;
}else{ // 엇갈리지 않았다면 i와 j를 교체 
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);
show();
return 0;

}