퀵정렬(quick sort)

자료 구조 정렬 중 하나의 기법이다.

퀵 정렬 방법을 설명해보겠다.

1.정렬할 숫자 중 하나를 pivot으로 지정한다.

2.pivot보다 좌측에 있는 숫자들을 좌측 맨 처음 숫자부터 L이라는 위치가 이동하면서 L값이 pivot보다 크면 정지한다.

3.pivot보다 우측에 있는 숫자들을 우측 맨 마지막 숫자부터 R이라는 위치가 pivot쪽으로 이동하면서 R값이 pivot보다 작으면 정지한다.

(L과R은 pivot을 넘어가지 못한다. 그러므로 교차할 일은 없다.)

4.L과 R이 모두 정지하면 L값과 R값의 값들만 서로 swap해준다.

(L과 R의 위치는 바뀌지 않는다.)

5.L과 R이 모두 pivot에서 정지할 때까지 2~4를 반복한다.

(반복 할 때 L과 R의 위치는 초기화하지 않는다.)

6.L과 R이 모두 pivot에서 정지하면 pivot값은 이제 고정위치로 결정한다.

7.고정위치가된 기존 pivot의 좌측과 우측은 각각 다시 1~6을 반복한다.

(나뉜 측의 숫자들이 없거나 1개이면 바로 고정 한다.) 

위의 설명이 퀵정렬 기본 설명이다.

옛날 대학교 1학년때 배운 책에서는 

pivot을 (첫 index + 끝 index) / 2 의 위치에 있는 값으로 했는데

이것은 무의미 한것이다.(pivot이라는 말 자체는 중심이라는 뜻이긴 하지만...)

L과 R의 정지에 따라 pivot도 위치가 옮겨다니므로

굳이 중간 위치에 있는 것을 가져다 안써도 된다는 것이다.

오히려 요즘 퀵정렬은 L과 R이 pivot과 만나면 멈추는 것을 이용하여

pivot 자체를 맨 첫값이나 맨 끝값으로 하여 처음 부터 L이나 R을 멈추고 시작한다.

맨 첫 값을 pivot으로 하면 L이 pivot이므로 L은 멈추고

R만 맨 우측에서 작은 것을 찾아 바꾸고 

그러면 다시 R이 pivot이 되어

L이 움직여 큰것을 찾아 멈추고 바꾸면 L이 다시 pivot이 된다. 

L과 R 중 하나만 체크하게 되니

하는 방법도 쉽고 설명도 쉬워 

요즘 퀵정렬은 이렇게 잘 사용되는 추세이다.

이 방식으로 한번 소스를 짜보겠다.

//시작=====================================================

#include <iostream>

using namespace std;

int LeftMove(int* _arr, int _pivot, int _left);

int RightMove(int* _arr, int _pivot, int _right);

//퀵정렬

void QuickSort(int* _arr, int _left, int _right)

{

int leftIdx = _left;

int rightIdx = _right;

//L인덱스를 초기 피벗 인덱스로 초기화

int pivotIdx = leftIdx;

//R탐색 시작

pivotIdx = RightMove(_arr, pivotIdx, rightIdx); //최종 피벗의 인덱스 리턴 받는다.

//최종 피벗 인덱스가 정해지고 좌측에 남은 항이 2개 이상일 경우 

//퀵정렬 재귀호출

if (pivotIdx - leftIdx > 1)

{

QuickSort(_arr, leftIdx, pivotIdx - 1); //L인덱스 부터 피벗 인덱스 전 까지

}

//최종 피벗 인덱스가 정해지고 우측에 남은 항이 2개 이상일 경우 

//퀵정렬 재귀호출

if (rightIdx - pivotIdx > 1)

{

QuickSort(_arr, pivotIdx + 1, rightIdx); //피벗 인덱스 다음부터 R인덱스 까지

}

}

//L탐색

int LeftMove(int* _arr, int _pivot, int _left)

{

int pivotIdx = _pivot;

int leftIdx = _left;

//L 인덱스가 피벗의 인덱스보다 작다면 루프

while (leftIdx < pivotIdx)

{

//L 값이 피벗 값보다 크다면

if (_arr[pivotIdx] < _arr[leftIdx])

{

swap(_arr[leftIdx], _arr[pivotIdx]); //서로 값 교환

pivotIdx = RightMove(_arr, leftIdx, pivotIdx - 1); //R탐색 - 최종 피벗 인덱스를 리턴받는다

break;

}

else

{

leftIdx++; //값이 작다면 좌측으로 이동

}

}

return pivotIdx; //최종 피벗 인덱스를 리턴

}

//R탐색

int RightMove(int* _arr, int _pivot, int _right)

{

int pivotIdx = _pivot;

int rightIdx = _right;

//R 인덱스가 피벗의 인덱스보다 크다면 루프

while (rightIdx > pivotIdx)

{

//R 값이 피벗 값보다 작다면

if (_arr[pivotIdx] > _arr[rightIdx])

{

swap(_arr[rightIdx], _arr[pivotIdx]); //서로 값 교환

pivotIdx = LeftMove(_arr, rightIdx, pivotIdx + 1); //L탐색 - 최종 피벗 인덱스를 리턴받는다

break;

}

else

{

rightIdx--; //값이 크다면 좌측으로 이동

}

}

return pivotIdx; //최종 피벗 인덱스를 리턴

}

void main()

{

int arr[] = { 17, 29, 10, 41, 5, 92, 34, 26, 3, 18 };    //숫자 배열

int size = _countof(arr);

QuickSort(arr, 0, size - 1);    //퀵정렬 함수

        //결과 출력 부분

for (int i = 0; i < size; i++)

{

cout << arr[i] << " ";

}

cout << endl;

}

//끝=====================================================

대략 적으로 위와 같이 짜게 됐는데

결과는 잘 나온다.

예전 기억으로는 pivot구하기부터 엄청 복잡하게 짰었는데

L이나 R을 pivot으로 고정 시키니 많이 간략해지고 쉬워진 느낌이다.

이론적이든 결론적이든

실제 퀵정렬을 시작할 때 pivot의 위치는 중요하지 않다.

그 pivot이 고정되게될 위치가 중요하다.

고정되는 위치가 딱 중간이 되면 가장 좋은 것이고

맨 끝으로 치우치게 되면 가장 안좋은 것이다.

퀵정렬은 처리가 숫자가 많아질수록 느려질 가능성이 커지는데

한 루프마다 반씩 줄어든다면 처리량도 반씩 줄어들 것이다.

그리고 나중엔 하나씩 남는다면 

루프를 더 돌리지 않고 고정 값이 하나 더 생기니 더 좋을 것이다.

하지만 pivot의 고정될 결과는 미리 알 수 있는 것이 아니니

최악과 최고의 시간 복잡도가 나뉘는 것임을 알아두자.