퀵 정렬(Quick sort)

이번에는 정렬 방법의 마지막 포스팅이자

평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법 인 

퀵 정렬(Quick sort)에 대해 알아 보겠습니다.

퀵 정렬(Quick sort)은 합병 정렬과 비슷하게 전체 리스트를 2개의 부분 리스트로 분할하고,

각각의 부분 리스트를 다시 퀵 정렬하는 전형적인 분할 정복 방법을 사용한다.

그러나 합병 정렬과는 달리 퀵 정렬은 리스트를 다음과 같은 방법에 의해 비균등하게 분할한다.

먼저 리스트 안에 있는 한 요소를 피벗(pivot)으로 선택한다.

여기서 피벗을 선택하는 방법은 여러가지가 있는데

1. 리스트의 가장 왼쪽(처음)

2. 리스트의 가장 오른쪽(마지막)

3. 리스트의 가운데

4. 가장 왼쪽, 가장 오른쪽, 가운데 값 중 중간 값

등 여러가지의 방법으로 피벗을 결정한다.

이렇게 피벗을 결정 한 뒤

피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 큰 요소들은 오른쪽으로 옮겨진다.

결과적으로 피벗을 중심으로 왼쪽은 피벗보다 작은 요소들로 구성되고,

오른족은 피벗보다 큰 요소들로 구성된다. 이 상태에서 피벗을 제외한

왼쪽 리스트와 오른쪽 리스트에서 피벗을 결정하고 위와 같은 방법으로 정렬을 반복하게 되면

전체 리스트가 정렬되게 된다.

위 그림은 리스트의 가장 왼쪽을 피벗으로 선택하는 방법으로 퀵 정렬을 하는 과정을 나타 낸 것이다.

그림에서 보는 것과 같이 피벗을 기준으로 피벗보다 작은 요소들은 피벗의 좌측 리스트로 

피벗보다 큰 요소들은 피벗의 우측 리스트로 옮겨진 것을 확인 할 수있다.

이러한 과정을 반복하면 최종 단계에서와 같이 전체 정렬이 된 것을 확인 할 수 있다.

위 그림은 피벗을 리스트의 가운데로 결정하는 퀵 정렬의 소스 코드이다.

위 소스 코드와 같이 간단하게 구현 할 수 있다는 것과

추가로 메모리 공간을 필요로 하지 않는다는 것이 퀵 정렬의 장점이다.

위 그림과 같이 피벗으로 인해 좌우의 리스트가 정확히 반씩 나뉘게 되는 경우가

퀵 정렬의 최선의 경우이고

위 그림과 같이 피벗으로 인해 한쪽의 리스트가 모두 포함되는 경우가

퀵 정렬의 최악의 경우이다.

최악의 경우 레코드의 수만큼 총 n번의 패스가 실행되고,

각 패스에서 n번의 비교가 이루어지게 되므로 비교 연산을 n^2번 실행하게 된다.

즉 퀵 정렬은 최악의 경우 의 시간 복잡도를 가지게 된다.

그럼에도 불구하고 퀵 정렬은 평균적인 경우의 시간 복잡도가 으로 나타난다.

특히 의 복잡도를 가지는 다른 정렬 알고리즘과 비교 하였을 때도

가장 빠른 것으로 나타났다. 이는 퀵 정렬이 불필요한 데이터의 이동을 줄이고

먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정 된 피벗들이 추후 연산에서

제외되는 특성 등에 기인한다고 보인다.

이상으로 퀵 정렬을 마지막으로 정렬 방법에 대한 포스팅을 마치겠습니다.

위 소스 코드를 직접 코딩해보려 노력하시길 바랍니다.