퀵 정렬(Quick Sort)

퀵 정렬은 이름처럼 굉장히 빠른 정렬 알고리즘이라고 알려져 있다. 이번 글에서는 이런 퀵 정렬을 어떻게 구현할 수 있는지, 항상 빠르게 작동하는지, 어떤 장단점이 있는지 알아보고자 한다.

퀵정렬?

퀵 정렬은 우선 한 원소를 무작위로 골라 기준으로 삼고, 배열을 분할한다. 그리고 고른 원소보다 작은 것들은 앞쪽으로, 큰 것들은 뒤로 보낸다. 이렇게 배열을 계속해서 분할하고 또 분할하면, 결국 배열은 정렬된 상태가 된다는 것이 퀵정렬의 기본적인 아이디어이다.

 

 

배열을 분할하는 기준값을 보통 pivot이라고 하는데, 이 pivot값이 무엇이냐에 따라 시간복잡도가 달라지기도 하기 때문에 이 값은 굉장히 중요하다. 보통은 첫번째 원소를 pivot값으로 설정하지만, 상황에 따라서는 중앙값이나 마지막값으로 두기도 하고 랜덤으로 설정하기도 한다.

 

분할 정복?

퀵 정렬은 분할 정복을 사용하는 알고리즘 중 하나이다. 분할정복은 문제를 작은 문제들로 쪼개고, 각각을 해결한 결과를 모아 원래의 문제를 해결하는 전략이다. 다시말해, 큰 문제를 작은 문제 여러개로 '분할'하고, 해결한 작은 문제들을 다시 모음으로써 원래의 큰 문제를 풀어내는 것이다.

분할 정복(divide & conquer) : 문제를 작은 문제들로 분할하고 각각 해결한 후 결과를 모아 원래의 문제를 해결하는 전략

 

퀵 정렬도 피벗을 기준으로 배열을 쪼개고, 쪼갠 배열을 정렬한 후 다시 모아 원래의 큰 배열을 만든다는 점에서 분할 정복 기법을 사용했다고 할 수 있다.

 

구체적으로 생각해보기

퀵정렬을 구현하는 구체적인 순서를 정리하면 아래와 같다.

 

1단계. 배열 중 원소 하나를 고른다. (pivot)

2단계. 배열을 두 부분으로 분할한다. pivot보다 작은 원소들은 앞쪽으로, 큰 원소들은 뒤쪽으로 분류한다.

   pivot보다 작은애들 || pivot || pivot보다 큰애들 → 대충 이런 모습이다.

 

3단계. 분할된 두 개의 배열에 이 과정(1,2단계)을 재귀적으로 적용한다.

 

pivot을 기준으로 분할을 하기 때문에, pivot의 위치는 더이상 바뀌지 않고 고정된다. 앞쪽에서는 pivot보다 작은 요소들이 자기들끼리 순서를 바꾸고, 뒤쪽에서는 pivot보다 큰 요소들이 자기들끼리 순서를 바꾸기만 하면 되는 것이다.

 

좀 더 생각해보면, 재귀 호출이 진행될 때마다 위의 과정 중 1단계를 거치게 되는데, 이 때마다 새로운 pivot이 등장하게 된다. 이 pivot도 마찬가지로 한번 지정되면 위치가 고정될 것이다. 그렇다면, 결국 재귀 호출 한번에 최소 한개의 원소(pivot)는 위치가 결정될 것이다. 이렇게 한 원소씩 위치가 결정되다보면, 모든 원소의 위치가 결정되는 순간이 올 것이고, 이 알고리즘은 언젠가 반드시 끝나게 된다.

 

최선의 경우, 최악의 경우?

최선의 경우

최선의 경우, 퀵정렬의 시간 복잡도는 O(nlog₂n)가 된다.

 

퀵정렬은 한 배열을 두 부분 쪼개는 과정을, 각 부분의 원소 개수가 1개가 될때까지 수행한다.

예를 들어 우선 배열의 원소 개수, 즉 n = 8이고 가운데 값을 pivot으로 지정한다고 가정해보자. 이 경우 몇번의 재귀 호출이 일어날까? 아래와 같이 모든 부분( |로 구분 )에 원소가 하나씩 들어갈 때 까지는 3번의 호출이 발생한다. 각 호출 단계의 pivot값은 빨간색으로 표시했다.

 

[1, 2, 3, 4, 5, 6, 7, 8]

→ [1, 2, 3 | 4 | 5, 6, 7, 8]

→ [1 | 2 | 3 | 4 | 5 | 6 | 7, 8]

→ [1 | 2 | 3 | 4 | 5 | 6 | 7 | 8]

 

재귀 호출이 일어날 때마다 n의 크기는 대략 절반이 된다. 이것을 일반화해보면 log₂n 번 정도 호출이 일어난다고 할 수 있다.

그렇다면, 재귀 호출 이후 각 배열에서는 몇번이나 비교연산이 이루어질까? 배열 대부분의 요소들을 서로 비교해야 하기 때문에 n번 정도의 연산이 발생하게 된다. 따라서 최선의 경우, 시간복잡도는 nlog₂n 이라고 할 수 있다.

재귀호출 횟수 * 각 배열의 비교 연산 = nlog₂n

 

최악의 경우

최악의 경우, 퀵정렬의 시간 복잡도는 O(n^2)가 된다.

 

pivot이 최솟값 혹은 최댓값인 경우에는 배열이 분할되지 않게 된다.

 

예를 들어 [1, 2, 3, 4]라는 배열이 있고, pivot은 배열의 가장 마지막값으로 지정한다고 가정해보자.

먼저 pivot은 4가 되고, 나머지 요소들은 모두 4보다 작기 때문에 앞쪽에만 몰리게 된다. 4의 자리는 그대로 고정된다.

위치가 고정된 4는 제외하고 나머지 [1, 2, 3]을 다시 정렬해보자. 이번에 pivot은 3이 될 것이다. 방금 전과 마찬가지로 3의 위치는 그대로 고정된다. 나머지 모든 요소에도 이런 과정이 동일하게 적용된다.

 

이 경우에도, 각 배열의 비교 연산 횟수는 최선의 경우와 동일하게 평균 n번 발생한다. 하지만 재귀 호출은 배열의 원소 수만큼 발생한다. 즉, 재귀호출 횟수는 n으로 늘어나게 된다. 따라서, 이렇게 배열이 오름차순이나 내림차순으로 정렬되어있는 경우에는 O(n^2)의 시간복잡도를 가지게 된다.

재귀호출 횟수 * 각 배열의 비교 연산 = n * n

 

퀵정렬의 장점, 단점

장점

시간적 측면에서 보면, 퀵정렬 방식을 사용하면 한 번 결정된 pivot들은 이후 연산에서 제외할 수 있고, O(nlog₂n)의 시간 복잡도를 갖는다. 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.

공간적 측면에서도, 배열 안에서만 위치를 교환하는 방식이기 때문에 다른 메모리 공간을 필요로 하지 않는다는 이점이 있다.

 

단점

앞서 말했듯 이미 정렬이 되어있는 배열에 적용할 경우, 괜히 여러번 분할을 하게 되어 오히려 수행시간이 더 길어질 수 있다는 단점이 있다.

 

 

최악의 경우에는 오히려 비효율적인 방법이 될 수도 있지만, pivot을 배열에서 랜덤하게 선택하면 평균적으로 O(n logn) 정도의 시간 복잡도를 갖기 때문에 어느정도 빠른 실행을 보장할 수 있다. 지금까지 분할정복의 좋은 예시이자, 빠른 정렬 알고리즘 중 하나인 퀵 정렬에 대해 알아보았다.