퀵소트 (Quick Sort)

다른 정렬 알고리즘과 다르게 비교를 줄여나가면서 진행되는 분할정복 알고리즘이다.

 

기본적인 틀은 아주 간단하다. 특정한 기준을 잡고 그것을 Pivot 이라고 부른다. pivot을 기준으로 pivot보다 작으면 왼쪽으로 이동하고, 크다면 오른쪽으로 이동하는 동작을 하게 된다.

이러한 배열이 만약 있다고 가정하고 돌아가는 원리를 설명해 보겠다.

 

arr[9]라는 배열을 하나 선언하고 그 Index값에 숫자를 넣었다. 표시해놓은 숫자 "7"(pivot)을 기준으로 arr[0]을 시작부터 비교를 하기 시작한다. 0번인 4와 7를 비교 했을때 만일 좌항이 pivot 보다 작다면 그대로 유지 시키고, 하나씩 비교를 해나아간다. 그리고 arr[3]을 가리키는 9의 값까지 도달했을시 pivot인 7이 더 작으므로 9과 7의 자리를 바꾸게 된다.

그리고 arr[6] = 5와 비교를 한다면 pivot인 7보다 작으므로 왼쪽으로 넘기면서 7과 자리를 바꾸게 된다. 이렇게 계속 바꿔나가면 어느순간 9는 arr[9] = 9에 자리에 오게되고 1 ~ 9 까지 오름차순으로 정리가 이루어지게 된다. 

 

과정을 다 거치면서 보면은 pivot을 기준으로 왼쪽에 있는건 무조건 작고 오른쪽 수는 무조건 크게된다.

당연한 소리지만 생각해보면 큰수들은 섞을 필요가 없기 때문에 연산 속도가 현저히 줄어들게된다.

 

만약 arr[9]짜리를 버블정렬로 나타냈다면 9 * 9 = 81번에 연산을 해야한다. 하지만 퀵소트를 사용한다면 절반이상에 연산속도를 줄여주므로 엄청난 효과를 가져오게된다.

 

구현은 재귀로 구현을 하는게 편리하며 Swap하는 과정으로 진행된다.

 

최악의 수가 발생하는 경우 = pivot 정렬순에 맞춰서 뽑혀 나오면 n(^2)이 된다.