퀵정렬 (Quick Sort)

가장 유명하고, 정렬 알고리즘의 표준이다시피 한 방법입니다. 실제로 코딩을 해 보면, 퀵 정렬이 코드가 가장 긴데, 실행 시간은 퀵 정렬이 다른 알고리즘들보다 기막힐 정도로 짧습니다. 

중간값이라는 뭔가 적당한(모호한) 값을 선택해야 하고, 최악의 경우 시간 복잡도가 O(n²)에 메모리 복잡도가 O(n)이 될 가능성까지 있는 알고리즘입니다.

중간값을 기준으로 데이터를 반으로 갈라 놓고, 양측에 대해서 재귀적으로 또 중간값을 설정해 정렬을 또 수행한다는 발상은 대단히 깔끔하고 멋집니다. 이런 걸 분할 정복법이라고 하지요. 이게 '퀵 정렬'이 아니었으면 '이분 검색'을 따라 '이분 정렬'이라는 이름이 붙었을 것입니다.

퀵 정렬은 본디 재귀적으로 정의되지만, 사용자 정의 스택을 구현해서 비재귀적으로 만들 수도 있으며, 본 소스 코드 역시 사용자 스택을 구현했습니다. 또한, 원소 개수가 한 자리 수로 떨어졌을 때는 또 재귀호출을 하는 게 아니라 삽입 정렬을 해서 능률을 극대화하기도 합니다.

 

1. #include <stdio.h>
2.  
3. void quick_sort(int *arr, int left, int right);
4.  
5. int main()
6. {
7. int arr[10] = {28,25,3,14,45,6,27,8,49,1};
8. int i = 0;
9.  
10. quick_sort(arr, 0, 9);
11.  
12. for(i=0; i<10; i++)
13. {
14. printf("%d ", arr[i]);
15. }
16. return 0;
17. }
18.  
19. void quick_sort(int *arr, int left, int right)
20. {
21. int i, j;
22. int temp;
23. int pivot = arr[left];
24.  
25. if(left<right){
26.  
27. i = left+1;
28. j = right;
29.  
30. while(i<=j)
31. {
32. while (arr[i] < pivot)
33. {
34. i++;
35. }
36. while (arr[j] > pivot)
37. {
38. j--;
39. }
40.  
41. if(i<j)
42. {
43. temp = arr[i];
44. arr[i] = arr[j];
45. arr[j] = temp;
46. }else{
47. break;
48. }
49. }
50. temp = arr[j];
51. arr[j] = arr[left];
52. arr[left] = temp;
53.  
54. quick_sort(arr, left, j-1);
55. quick_sort(arr, j+1, right);
56. }
57. }

결과 : 1 3 6 8 14 25 27 28 45 49