그림으로 알아보는 퀵 정렬 (quick sort)

퀵 정렬

퀵 정렬의 원리는 생각보다 간단하다.

사람들을 키 순서대로 정렬하려고 해보자. 

우선 기준이 되는 한 명을 뽑고,

기준보다 작은 사람들은 순서에 상관없이 왼편에, 

기준보다 큰 사람들은 순서에 상관없이 오른편에 세운다.

기준이 되는 한 사람을 제외하면 2개의 부분배열로 나누어지게 되는데,

만들어진 부분배열에 다시 똑같은 작업을 반복한다.

계속해서 배열을 2부분으로 쪼개다보면,

부분배열의 크기가 0 또는 1인 경우가 나오게되는데,

크기가 0 또는 1인 부분배열은 "더 이상 정렬의 필요성이 없는 배열" 이므로,

"정렬이 완료된 상태의 배열" 로 해석할 수 있다.

정리하자면,

퀵정렬은 2개의 부분배열로 나누고,

정렬 필요성이 있는 부분배열에 다시 퀵정렬을 적용하는 과정이다.

퀵 정렬의 시간 복잡도

퀵 정렬은 피벗을 기점으로 2개의 그룹으로 나누는 작업을 반복하며,

피벗이 얼마나 배열을 균등하게 나누느냐에 따라 성능이 크게 좌우된다.

최선의 경우는 모든 상황에서 두 그룹으로 균등하게 나누어진 경우이며,

이 경우의 시간 복잡도는 O( log(n) ) 이다.

최악의 경우는 모든 상황에서 한 그룹에 모든 요소가 몰렸을 경우이며,

아래의 그림과 같이 버블정렬과 똑같은 동작이 실행되므로,

이 경우의 시간 복잡도는 O( n^2 ) 이다.

즉 퀵 정렬의 성능을 향상시키려면

최대한 균등하게 나눌 수 있는 피벗을 선택해야 한다.

최선의 피벗을 선택하는 방법은 여러가지가 있으며,

보편적으로 중간값이나 평균값이 사용된다.

최적의 피벗을 구할 수 있는 방법은 현재도 연구중이며,

중간값이나 평균값을 피벗으로 선택했을 경우,

퀵정렬의 평균 시간 복잡도는 O( n*log(n) )으로 알려져있다.

알고리즘 구현

퀵 정렬을 구현하는 방법은 간단하다.

• 피벗보다 작은 요소를 왼쪽부터 채운다,

• 피벗보다 큰 요소를 오른쪽부터 채운다,

• 나누는 과정이 끝나고 각 그룹에 대해 다시 퀵 정렬을 적용.

• 크기가 0이거나 1인 그룹은 정렬된 것으로 보고 무시한다.

 

아래는 위의 과정을 그림으로 나타낸 것이며,

피벗으로 구간의 마지막 요소를 선택했다.

노란색은 피벗보다 작은 요소가 채워질 공간이고,

회색은 피벗의 위치인 동시에, 피벗보다 큰 요소가 채워질 공간이다.

푸른색은 노란색과 회색이 겹쳐진 것을 의미한다. (종료조건)

코드