퀵 정렬(Quick-Sort)

퀵 정렬(Quick-Sort)

- 퀵 정렬은 평균 수행시간이 O(n log n)으로 매우 효율적인 정렬이다.

- 최악의 경우에는 O(n^2)의 시간까지 걸리기도 한다.

동작원리

 - 배열의 가장 끝 원소를 키값으로 삼아 배열의 첫 원소부터 비교해 작은 범위와 큰범위로 나누어 나누어진 범위에 대해 다시 정렬을 하는 원리로 동작한다.

소스 

- partition 함수

1. /*
2.  퀵정렬을 하기위해 내부에서 재배치하는 함수
3.  기준값보다 큰값이오면 j 범위에 넣고 작으면 i 범위에 넣어 배치
4. */
5. int partition(int *arr,int a , int b)
6. {
7.     int x = (*(arr+b));
8.     int i = a-1;
9.     int j = 0;
10.     int temp = 0;
11.  
12.     for(j=a; j<b; j++)
13.     {
14.         if( (*(arr+j)) <= x) // j 부분의 값을 검사 기준값 보다 작을시 i 범위에 넣기위해 값을 교체
15.         {
16.             i = i+1;
17.             temp = (*(arr+i));
18.             (*(arr+i)) = (*(arr+j));
19.             (*(arr+j)) = temp;
20.         }
21.     }
22.  
23.     // 기준값을 j범위의 첫 요소와 교체
24.     temp = (*(arr+i+1));
25.     (*(arr+i+1)) = (*(arr+b));
26.     (*(arr+b)) = temp;
27.  
28.  
29.  
30.         return i+1; //교체한 기준값을 포함한 i 범위를 반환
31. }

- quicksort 함수

1. /*
2. 퀵 정렬하는 함수
3. */
4. void quicksort(int *arr,int a, int b)
5. {
6.     int q = 0;
7.  
8.     if(a<b)
9.     {
10.         q = partition(arr,a, b);
11.  
12.         quicksort(arr,a, q-1); // 기준값을 뺀 나머지 i 범위를 정렬
13.         quicksort(arr,q +1, b); // 기준값을 뺀 나머지 j 범위를 정렬
14.     }
15.  
16. }

결과