|
#include <iostream>
using namespace std;
void interChange(int* list, const int left, const int j) { int temp = list[left]; list[left] = list[j]; list[j] = temp; }
void printList(int* list) { for (int i = 0; i < 10; i++) cout << list[i] << " ";
cout << endl; }
void quickSort(int* list, const int left, const int right) { if (left < right) { int i = left, j = right + 1, pivot = list[left];
do { do i++; while (list[i] < pivot); do j--; while (list[j] > pivot);
if (i < j) { interChange(list, i, j); } } while (i < j);
interChange(list, left, j);
quickSort(list, left, j - 1); quickSort(list, j + 1, right); } }
int main() { int list[10] = {26, 5, 37, 1, 61, 11, 59, 15, 48, 19};
quickSort(list, 0, 9);
printList(list); }
|
위 코드는 Fundamentals of Data Structure in C++ - Horowitz에 나오는 Quick Sort 알고리즘을 이용하여 프로그래밍 하였다.
Quick Sort는 임의의 값을 기준으로 하고, 그 값의 좌우로 작은 값과 큰값을 분리한 후, 좌우를 다시 Quick Sort로 정렬하는 것이다.
함수 interChange는 주어진 두 개의 위치의 값을 배열에서 바꾸는 역할을 한다.
quickSort함수는 배열과 배열의 시작위치, 끝위치를 파라미터로 전달받아 정렬하는 역할을 한다.
시작위치, 끝위치를 받는 이유는 배열을 pivot을 중심으로 계속 나누어 정렬하기 때문이다.
우선 시작에서 left가 right보다 작은 지를 확인한다. 그렇다는 것은 정렬할 배열이 존재한다는 것이다.
그렇지 않다는 것은 배열의 정렬이 끝났다는 것을 의미한다.
정렬할 배열이 있다면,
우선 시작과 끝 위치를 각각 새로운 변수 i, j에 넣어주는데, 이 때 j의 값은 끝 위치에서 +1을 해준다.
그 이유는 j의 위치부터 시작하는 것이 아니라, 하나 빼 준 상태에서 비교를 시작하기 때문이다.
그리고, 기준점이 되는 pivot의 위치는 배열의 시작위치의 값으로 임의로 정해준다.
만약 pivot을 시작위치가 아닌 다른 위치의 값으로 사용하고 싶다면, 위의 코드에서 비교 부분을 좀 수정해줘야 할 것이다.
do while 부분은 비교하는 부분이다.
i는 배열의 앞에서부터 시작하여 pivot의 값보다 작은 지를 비교하고, 크다면 뒤로 보내야 하니 반복문을 종료한다.
j는 배열의 뒤에서부터 시작하여 pivot의 값보다 큰 지를 비교하고, 작다면 앞으로 보내야 하니 반복문을 종료한다.
이렇게 비교를 종료한 i와 j의 값을 비교하여 i가 j보다 작다면, 두 개의 값을 교환한다.
위의 예에서 pivot의 값은 26이 되고, 첫 반복문에서 i는 배열 1의 위치에서 시작하여, 값 5와 26을 비교한다.
5가 작으므로 i는 1이 증가되고, 배열 2의 위치의 값 37과 26을 비교한다.
값이 pivot보다 크므로 이 값은 뒤로 보내야 한다.
그래서, 반복문을 중단하고 i의 값은 2가 된다.
j는 9의 위치에서 시작하여 19와 26을 비교한다.
19가 26보다 작으므로 이 값은 앞으로 보내야 한다.
그래서, 반복문을 중단하고 j의 값은 9가 된다.
두 반복문이 중단되었으므로, i와 j의 값을 비교하고, 아직 i가 j보다 작으므로 두 위치의 값들을 교환한다.
그리고 다시 비교 반복을 시작한다.
i는 3으로 증가하고 값은 1이다.
26보다 작으므로 i는 4로 증가하고 값은 61이 된다.
26보다 크므로 i는 4에서 반복을 종료한다.
j는 8로 감소하고 값은 48이 된다.
26보다 크므로 j는 7로 감소하고 값은 15가 된다.
26보다 작으므로 j는 7에서 반복을 종료한다.
두 반복문이 중단되었으므로, i와 j의 값을 비교하고, 아직 i가 j보다 작으므로 두 위치의 값들을 교환한다.
그리고 다시 비교 반복을 시작한다.
i는 5으로 증가하고 값은 11이다.
26보다 작으므로 i는 6으로 증가하고 값은 59가 된다.
26보다 크므로 i는 6에서 반복을 종료한다.
j는 6으로 감소하고 값은 59가 된다.
26보다 크므로 j는 5로 감소하고 값은 11이 된다.
26보다 작으므로 j는 5에서 반복을 종료한다.
두 반복문이 중단되었으므로, i와 j의 값을 비교하고, i가 j보다 크므로 반복을 마친다.
이제 j의 위치와 pivot의 위치의 값을 바꾸면, pivot을 중심으로 좌측은 작은 값들을 모아놓고 우측은 큰값들을 모아놓았다.
이 배열을 pivot을 중심으로 좌/우로 구분지어 다시 위의 정렬을 이어나간다.
이런식으로 정렬이 이루어지게 된다.