퀵 정렬(Quick-sort)

퀵정렬은 분할정복(Divide-Conquer)기법을 이용하여 데이터를 정렬하는 정렬 알고리즘이다.

분할정복이란 해결해야 할 부분을 분할하여 문제를 해결하는 방법이다.

퀵정렬은 기준이 되는 pivot을 설정하여 pivot을 기준으로 작은 값은 왼쪽으로 큰 값은 오른쪽으로 이동하여 원소를 정렬한다.

pivot의 왼쪽에는 pivot보다 작은 값이 와야하고 pivot의 오른쪽에는 pivot보다 큰 값이 와야 한다. 그래서 Left와 Right를 통해 반대쪽으로 날려보낼 값을 찾을 것이다.

또한 Left와 Right가 만나는 지점은 Pivot과 swap이 되는 자리이고 교체된 자리가 기존 pivot값의 올바른 위치가 된다.

pivot을 설정하는 방법은 유일하지 않지만 여기선 가운데 위치를 pivot으로 잡았다.

초기상태는 아래와 같다.

Left와 Right를 한칸씩 이동하여 swap할 값을 찾아야 한다.

Left는 pivot보다 크거나 같은 값을 찾으면 멈출 것이고 Right는 pivot보다 작은 값을 찾을 때 멈출 것이다.

Left는 7로 pivot보다 크기 때문에 움직이지 않는다. 이제 Right를 움직여야 한다.

Right를 한칸 이동시켰을 때 pivot보다 작은 4를 찾았다.

Left와 Right 둘다 원하는 값을 찾았기 때문에 둘을 swap한다.

다시 Left와 Right를 한칸씩 움직여서 원하는 값을 찾는다.

Left가 움직이면서 3은 pivot보다 작기 때문에 pass하고 16에서 stop하였다.

Right가 움직이면서 pivot보다 작은 값을 찾지 못하고 Left를 만나게 되었다.

Left와 Right가 만나는 지점인 16이 Pivot과 교체될 자리이며 Pivot이였던 5의 올바른 위치가 된다.

기존 Pivot이였던 5가 제자리를 찾은 모습이다.

5를 기준으로 왼쪽 부분집합은 5보다 모두 작고, 오른쪽 부분집합은 5보다 모두 큰 것을 알 수 있다.

앞서 퀵정렬은 분할정복 기법을 사용한다고 언급하였다. 5를 기준으로 정렬할 부분이 분할된 것이다. 

왼쪽 부분집합과 오른쪽 부분집합을 따로따로 처리해주면 된다. 두 부분을 동시에 고려할 필요가 사라진 것이다.

왼쪽 부분집합에서 다시 Pivot, Left, Right를 설정하여 위의 과정을 반복한다.

Left는 Pivot보다 큰 값을 찾아야 하므로 오른쪽으로 이동해야 한다.

Left는 Pivot보다 큰 값을 찾지 못하고 끝에서 멈췄다. (3이 마지막 위치인 이유는 5의 왼쪽 부분집합은 index 0~1이기 때문)

Right는 Pivot보다 작은 값인 3에 위치하고 있었기 때문에 제자리를 찾았다.

결국 Left와 Right가 같은 위치에 놓이게 되었다.

그럼 Pivot과 swap해야 한다.

swap을 통해 기존 Pivot이였던 4가 올바른 자리에 놓이게 되었다. (올바른 자리를 찾은 값은 초록색 박스에)

4의 왼쪽 부분집합인 3은 원소가 1개이기 때문에 위의 과정을 더이상 수행하지 않는다.

이제 5의 왼쪽 부분집합은 모두 제자리를 찾은 것이다.

다음으로 5의 오른쪽 부분집합을 정렬해보자

Left는 처음에 16으로 Pivot보다 크므로 stop하고 Right를 이동하여 Pivot보다 작은 값인 7을 찾아 둘을 swap한다.

16과 7을 swap하였고 Left와 Right가 한칸씩 이동하였다.

이제 다시 Left를 움직일 것이다.

Left가 한칸 이동하였더니 Left와 Right가 같은 위치에 놓이게 되었다. 이제 Pivot과 swap한다.

Pivot이 (Left=Right)와 같은 위치에 있으므로 현재 자리가 11의 올바른 자리가 된다.

11이 올바른 위치에 놓이게 되었고 11을 기준으로 정렬되지 않은 왼쪽 부분집합과 오른쪽 부분집합으로 분할되었다.

왼쪽 오른쪽 부분집합(노란색 박스)에 대해 똑같이 Pivot, Left, Right를 통해 정렬시켜주면 정렬이 끝난다.

왼쪽 부분집합인 7, 9를 정렬하면 

Pivot 7의 올바른 위치를 찾았고 7의 왼쪽 부분집합은 공집합이며 오른쪽 부분집합의 원소는 1개이므로 7의 위치가 정해지면서 9의 위치도 정해진다.

이제 11의 오른쪽 부분집합 16, 13만 정렬해주면 된다.

Left는 Pivot과 같으므로 제자리를 찾았고 Right 역시 Pivot보다 작기 때문에 Left와 Right를 swap한다.