알고리즘) 퀵 정렬(Quick Sort) 개념과 C구현

 

퀵정렬(Quick sort)

 

퀵정렬은 대표적인 분할정복 알고리즘중에 하나이다.

분할정렬이란 하나의 특정한 값을 기준으로 양 쪽을 나눠서 정렬하는 것이다.

 

퀵정렬은 운이좋으면 아주빠르게 처리되기때문에 붙은이름이며

평균적으로 시간복잡도가 O(N * logN) 입니다.

 

 

 

3 7 8 1 5 9 6 10 2 4을 오름차순으로 정렬하시오

 

▶퀵 정렬

풀기 어려운 큰 문제를 작은 문제로 나누어 푸는 분할 정복을 이용합니다. 방법은 아래와 같습니다.

1. 입력 받은 리스트에서 기준이 되는 값인 pivot을 설정한다.

2. pivot을 기준으로 pivot보다 작은 값은 왼쪽에, 큰 값은 오른쪽에 옮겨진다.

3. 왼쪽, 오른쪽 리스트의 크기가 1이 될 때까지, 1,2번을 반복한다.

 

이러한 정렬을 퀵소트를 통해 정렬시킬수 있습니다.

 

퀵정렬은 피봇이라는 기준값을 사용하는데 보통 첫번째 값을 피봇으로 사용합니다. 위에 예시를 봤을때 

 

 

3 7 8 1 5 9 6 10 2 4

1. 맨앞에 있는값(3)을 피봇으로 설정합니다

왼쪽부터(7부터) 피봇값(3)보다 큰값을 찾습니다.

오른쪽(4)부터 피봇값(3)보다 작은값을 찾습니다.

큰값은 7, 작은값은 2가 될것이며

둘의 위치를 바꿔 줍니다.

 

3 2 8 1 5 9 6 10 7 4

2. 또다시 피봇은 3인채로 똑같이 왼쪽부터 큰값을, 오른쪽부터 작은값을 찾습니다.

큰값은 8 작은값은 1이 될것입니다.둘의 위치를 바꿔줍니다.

 

3 2 1 8 5 9 6 10 7 4

 

 

3. 또 피봇은3인채로 왼쪽부터 피봇보다 큰값을, 오른쪽부터 피봇보다 작은값을 찾습니다.

큰값 8 , 작은값 1이 발견될텐데 이때 작은값의 인덱스가 큰값의 인덱스보다 작습니다.

따라서 피봇값과 작은값은 자리를 바꿔줍니다. 이를 엇갈렸다고 표현하겠습니다.

엇갈렸을때 피봇값과 작은값의 자리를 바꾸는데 그 바꾼후 피봇값(3)은 자리가 고정이 됩니다.

왜냐하면 3의 왼쪽에는 자기보다 작은값만존재하고 , 오른쪽에는 자기자신보다 큰값만 존재하기 떄문

 

1 2 3 8 5 9 6 10 7 4

4. 피봇값3을 기준으로 배열은 반으로 쪼개서 방금까지 했던 작업들을 각각 합니다.즉 왼쪽(1 2 ) 부터 생각하면

 

1 2

4-1(왼쪽) 1을 피봇으로 설정하고 왼쪽부터 피봇값(1)보다 큰값을 오른쪽부터 피봇값(1)보다 작은값을 찾습니다.

큰값은 2, 작은값은 1(자기자신) 이떄 작은값의 인덱스가 큰값의 인덱스보다 작으므로 마찬가지로 작은값과 피봇의 인덱스를 바꿔줍니다(즉 작은값1, 피봇값1 이므로 변화는없습니다)  엇갈렸으므로 1은 자리가 고정이되고

1의 왼쪽값들을 퀵소트해주는데 왼쪽값이 없으므로 생략,

1의 오른쪽값들을 퀵소트해주는데 값이 2 하나이므로 2도 자리가 고정이되며

1, 2 3 은 자리가 확정이됩니다.

이제 아까3의 오른쪽값들을 퀵소트해줍니다.

 

8 5 9 6 10 7 4

 

4-2(오른쪽)  피봇을 첫번째값(8)로 설정하고 왼쪽부터 피봇값(8)보다 큰값을 오른쪽부터 피봇값(8)보다 작은값을 찾습니다.

큰값9, 작은값 4가 정해질것이며 둘의 자리를 바꿉니다.

8 5 4 6 10 7 9

 

4-3 또 피봇값(8)보다 왼쪽부터 큰값을, 오른쪽부터 작은값을 찾습니다. 

작큰값은 10, 작은값은 7 둘의 자리를 바꿉니다.

 

8 5 4 6 7 10 9

4-4 피봇값보다 왼쪽부터 큰값을 오른쪽부터 작은값을 찾습니다.

큰값은 10이며 작은값은 7 

이떄 작은값의 인덱스가 큰값의 인덱스보다 작으므로 엇갈렸다고 표현할수있습니다.작은값과 피봇과 자리를 바꿉니다.

 

 

7 5 4 6 8 10 9

4-5 8은 자리가 고정이 되었고 이제 8을 기준으로 왼쪽 7 5 4 6을 퀵소트해주고 

8의 오른쪽 10 9를 퀵소트 해줍니다.

 

 

7 5 4 6 

맨앞의 값을 피봇으로 정하고 왼쪽부터 큰값을 오른쪽부터 작은값을 찾습니다.

이떄 작은값6과 큰값x

이떄도 엇갈렸다고 표현하는데 피봇과 작은값의 자리를 바꿔주고 7은 자리가 고정이되며바꾼 피봇값의 자리를기준으로 왼쪽 오른쪽을 나눠서 퀵소트를 진행해줍니다.

5 4 6 7

 

 

 

5 4 6 

 

5를 피봇으로 왼쪽부터 큰값 오른쪽부터 작은값을 찾습니다.

큰값6 작은값 4엇갈렸으므로 작은값과 피봇값의 자리를바꾸고 바꾼 피봇값은 고정이되며 또 왼쪽 오른쪽을 나눠서 퀵소트를 진행

 

 4 5 6 

5는 고정된값이며 왼쪽값이 하나이므로 4도 고정

5의 오른쪽도 정렬할 값이 하나이므로 6도 고정

 

 

7 5 4 6 8 10 9 여기서 왼쪽값들을 전부 정렬했습니다. 따라서 현재               1 2 3 4 5 6 7 8 10 9 이며 피봇값8의 오른쪽을 퀵소트 해면 정렬이 완료됩니다.

소스코드 

 

#include <stdio.h>
 
int number = 10;
int data[] = {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; // 키는 첫 번째 원소
   int i = start + 1, j = end, 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;
}