퀵정렬(Quick Sort)이란?

1. 퀵정렬(Quick Sort)이란?

-. 교환정렬의 일종이며 분할-정복법(divide and conquer)에 근거한다.

-. 정렬할 리스트를 두개로 분할하고 정렬하는 방법이다.

-. 축(pivot)값을 기준으로 정렬하는데, 축값을 중심으로 축값보다 큰 값은 오른쪽 리스트에

   작은 값은 왼쪽리스트로 이동시킨다. (첫번째의 데이터를 축값으로 한다.)

-. 오른쪽 리스트와 왼쪽 리스트부분은 독립적인 단위로 정렬하여 오른쪽 리스트부분에 대한

   새로운 분할 축값을 선택하여 두 부분으로 분리하고, 왼쪽 리스트부분 역시 새로운 축값을

   선택하여 두 부분으로 분리하는 과정을 반복하는데 리스트들은 재귀적 방법으로 각각 재배열

   하는 방식이다.

-. 각 분할 자료개수가 1이 되면 정렬은 완료된다.

 

2. 퀵정렬을 이용하여 오름차순으로 정렬하는 방법

 

3. 퀵정렬의 비교회수

-. 최선일 경우의 비교회수 공식 : N - 1

-. 최악일 경우의 비교회수 공식 : N(N – 1)/2

-. 위의 그림을 보시면 아시겠지만 제일 처음에는 (N – 1)번을 비교하고,

   그 다음에는 (N – 2)번 만큼 비교하고, 그 다음은 (N – 3)번을 비교하면서 비교회수가 1이 될

   때까지 이 작업을 반복할 것이다.

-. 비교회수는 (N – 1) + (N – 2) + (N – 3) …… + 1 이 될 것이다.

   최대 (N – 1)번을 수행할 것이며, 각 패스가 수행할 때마다

   수학식으로 표현하면   이므로 공식은 N(N – 1)/2 이런 공식이 성립된다.

 

4. 퀵정렬의 연산시간

  -. 연산시간 공식(평균) : 0(n log n)

  -. 연산시간 공식(최악이 경우) : O(n²)

-. 연산시간을 표기하는 방법은 일반적으로 사용하는 O표기법인데, 이 O표기법은 ‘최악의 경우’

   (Worst Case)에 대한 연산시간을 나타낸다.

  

5. 퀵정렬의 장점

-. 정렬할 데이터가 이미 준비되어 있고 모든 데이터들을 정렬해야 할 경우에 가장 빠른

   수행속도를 보여준다.

 

6. 퀵정렬의 단점

-. 축(pivot)값이 같은 것끼리는 순서관계가 파괴된다.

   (중요한 데이터의 경우에는 퀵정렬을 사용하지 않는 것이 좋다.)

-. 안정성이 없다.

 

7. 퀵정렬을 이용해서 작성한 예제

#include "stdio.h"   void Quick_Recursive(int parm_data[], int parm_left, int parm_right);   void Quick_Sort(int parm_data[], int parm_count) {     Quick_Recursive(parm_data, 0, parm_count - 1); }   void Quick_Recursive(int parm_data[], int parm_left, int parm_right) {     int pivot, left_hold, right_hold;     left_hold = parm_left;     right_hold = parm_right;       // 0번째 원소를 pivot으로 선택한다.     pivot = parm_data[parm_left];       while(parm_left < parm_right){         while((parm_data[parm_right] >= pivot) && (parm_left < parm_right)) parm_right--;         if(parm_left != parm_right){             parm_data[parm_left] = parm_data[parm_right];         }           while((parm_data[parm_left] <= pivot) && (parm_left < parm_right)) parm_left++;         if(parm_left != parm_right){            parm_data[parm_right] = parm_data[parm_left];            parm_right--;         }     }       parm_data[parm_left] = pivot;     pivot = parm_left;     parm_left = left_hold;     parm_right = right_hold;       if(parm_left < pivot) Quick_Recursive(parm_data, parm_left, pivot - 1);     if(parm_right > pivot) Quick_Recursive(parm_data, pivot + 1, parm_right); }   void main() {     int array[10] = {27, 4, 37, 2, 62, 12, 59, 16, 49, 18};     int i;       printf("=== 퀵정렬하기 전 ===\n\n");     for(i = 0; i < 10; i++) printf("%d   ", array[i]);     printf("\n\n");     printf("================================");     printf("\n\n");       Quick_Sort(array, 10);     printf("=== 퀵정렬한 후 ===\n\n");     for(i = 0; i < 10; i++) printf("%d   ", array[i]);     printf("\n\n"); }

 

  결과는 아래와 같습니다.

출처 : 팁스소프트