[자료구조] 6-3. 쾌속(Quick) 정렬

퀵 소트는 분할 정복 알고리즘에서 결합을 요구하지 않는 2단계 짜리 분할 정복 알고리즘이다. 분할을 잘 하면 결합이 필요하지 않다는 것이 기본 아이디어다.

퀵 정렬은 결합을 요구하지 않도록 리스트를 적절하게 분할하겠다고 하는 것이다.

리스트를 분할할 때 기준이 되는 값을 pivot이라고 부른다. pivot을 기준으로 왼쪽은 pivot보다 작은 수,  오른쪽에는 pivot보다 큰 수만 오도록 분할한다. 이것을 split 혹은 partition이라고 부른다.

합병 정렬이 좌우의 요구 조건 없이 그냥 반으로 쪼개는 것이라면, 퀵 정렬의 split은 pivot을 기준으로 왼쪽에는 pivot보다 작은 수, 오른쪽에는 pivot보다 큰 수가 오도록 분할한다.

따라서 퀵 정렬에서는 split 알고리즘이 매우 중요하다. 리스트의 가장 첫 번째 원소를 pivot이라고 설정하고 pivot의 왼쪽에는 더 작은 값을, 오른쪽에는 큰 값을 배치하도록 2개의 while 루프를 수행한다.

과정을 단계별로 살펴보자. s인 16이 pivot이 되고 left 포인터는 s의 다음값, right 포인터는 e라고 불리는 마지막 원소로 초기화 된다.

left는 오른쪽으로 지나가면서 pivot 보다 큰 값에서 멈춘다. pivot 보다 작은 값만 왼쪽에 와야하기 떄문이다. right는 오른쪽에서 왼쪽으로 움직이면서 pivot보다 더 작은 값에서 멈춘다. 그리고 left와 right가 멈췄던 두 값의 자리를 서로 바꿔준다.

첫번째 while문은 right의 이동을 지시한다. 즉, right 값이 pivot보다 크거나 같으면서 left보다 작거나 같은 동안은 right를 감소시킨다.

그림을 보면 27과 20은 pivot보다 크므로 이동하다가 4에서 멈추게 된다.

두번째 while은 left의 이동을 지시한다. pivot보다 작고 right보다 작거나 같은 동안 이동한다. 그래서 38에 멈춘다.

멈춰있는 상태에서 right가 더 오른쪽에 있다면 left와 자리를 바꾼다.

그래서 이렇게 변경된다. 아직 left가 right의 왼쪽에 있기 떄문에 루프의 처음으로 돌아가서 연산을 수행한다.

이제 right가 pivot보다 작은 4에서 멈춘다.

 left는 pivot보다 큰 수인 19를 만나기도 했고, 또 right 보다 더 크기 때문에 19에서 멈춘다. 이 둘은 right가 더 크지 않기 때문에 자리를 바꾸지 않고 끝난다.

그러면 마지막으로 right와 pivot이 자리를 바꾼다.

그럼 pivot은 네번째 자리가 된다. 

이렇게 바뀌니까 pivot을 기준으로 왼쪽은 작은 값, 오른쪽은 큰 값이 들어가게 된다.

합병 정렬에서는 divide를 하고 나면 n개짜리 배열이 n/2개짜리 배열 2개가 됐다. 그런데 퀵 정렬에서는 split을 해서 n/2개 짜리 2개가 되는 것이 아니다. pivot이 가장 작은 값이라면 왼쪽에는 배열이 없고, 오른쪽에는 n-1개짜리가 남는다.

만약 이 상태에서 4를 pivot으로 split한다면 다른 원소들은 다 오른쪽에 있어야 한다. 4가 가장 작은 값이기 때문이다. 이런 경우가 바로 worst case이다.

코드를 보면, 먼저 split을 하고 왼쪽과 오른쪽에 대해 각각 정렬을 수행한다.

합병 정렬에서는 s==e일때 예외처리를 한다. 하지만 퀵 정렬에서는 s가 더 클 수도 있는 상황이 발생한다.

이러한 배열에 대해 퀵 정렬은 16을 pivot으로 왼쪽에 작은 수, 오른쪽에 큰 수를 배치한다. 이러한 분할이 끝나면 각각에 대해 정렬을 수행하는 과정을 정복이라고 한다. 그러고 나면 이미 더 작은 수, pivot, 더 큰 수가 모여있기 때문에 결합이 필요없는 특징이 있다. 

과정을 자세히 살펴보자. 0에서 7까지 쾌속 정렬을 진행한다.

pivot의 위치는 3이 된다.

0에서 부터 7까지의 쾌속 정렬은 0에서 2까지와 4에서 7까지로 나뉘어서 호출된다.

qs(0,2)를 진행하면 pivot이 가장 작은 숫자인 4이다. 여기서 s는 0이고 e는 2다. 

원래 왼쪽은 s에서부터 m-1까지, 오른쪽은 m+1에서부터 e까지 수행되어야 하는데 m=0이므로 0에서 -1까지, 1에서 2까지 수행해야 하는 상황이 됐다. 이런 경우에는 예외처리를 해서 정렬을 수행하지 않고 끝내게 된다.

이제 qs(1,2)는 해오던 대로 퀵정렬을 수행하면 된다.

pivot은 이제 12가 되었다.

그럼 12는 이동하고 m=2가 된다.

그럼 또 마찬가지로 s=1, e=2, m=2인데 s부터 m-1까지, m+1부터 e까지 수행해야 하므로 qs(1,1)과 qs(3,2)로 정렬한다.

하지만 qs(1,1)은 1에서부터 1까지가 되므로 예외처리로 수행하지 않는다.

qs(3,2) 또한 예외처리에 걸려 수행되지 않고 끝난다.

뒤쪽도 마찬가지로 보면 된다.

이렇게 결합 과정 없이 정렬된다.

퀵 정렬의 시간 복잡도는 계산이 꽤 복잡하다. 분할하는 데 걸리는 시간이 O(n)이라면 실제로 분할된 2개의 왼쪽, 오른쪽 배열의 크기가 다르기 때문에 모든 경우에 대해서 다 계산을 하고 그때의 경우를 1/n을 곱해서 평균적인 경우를 계산해야 한다.

이 점화식을 풀면 O(n log n)이 나온다. 그럼 합병 정렬과 시간이 비슷한 것으로 생각할 수 있는데, 많은 실험 결과 퀵 정렬이 조금 더 빠르다고 알려져있다. 그래서 이름이 퀵 정렬인 것이다!

첫번째처럼 pivot이 전체 숫자의 가운데로 파고들 수 있는 경우에는 성능이 좋다. 하지만 두번째 처럼 pivot이 최솟값이나 최댓값이 들어 있어서 결국 0개와 n-1개로 분할되는 경우에는 최악의 경우인 O(n²)이 걸린다. 평균은 똑같이 O(n log n)이 걸리게 된다.

그에 비해서 합병 정렬은 꾸준히 O(n log n)을 유지한다는 장점이 있다.

이제 O(n²) 정렬 알고리즘과 O(n log n) 정렬 알고리즘으로 설명하기 힘든 정렬 알고리즘을 알아보자.

정렬 알고리즘은 내부 정렬과 외부 정렬로 나눌 수 있다. 내부 정렬은 데이터를 모두 메인 메모리에 올려서 정렬한다. 외부 정렬은 보조 기억장치를 이용해 정렬한다.

기타 알고리즘으로는 다양한 종류가 있지만 그 중 제일 많이 쓰이는 쉘과 기수 정렬을 알아보겠다.

쉘 알고리즘은 일반화된 삽입 정렬이다. 정렬을 여러 개의 부분 배열로 분할한 다음, 각각에 대해 삽입 정렬을 수행하고 그 결과를 통합한다.

예를 들어, 12개의 숫자를 크기 3개짜리의 4개 배열로 나눠보자. 

그래서 (세로로 보면) 4개의 배열이 생긴다. 그리고 이 각각을 정렬한다. 그러면 5,9,4는 4,5,9 이런식으로 정렬이 된다.

그리고 나서 4개의 정렬된 결과를 2개로 통일한다. 그 다음에 다시 각각을 정렬한다.

이 과정을 반복하면 이렇게 정렬이 되는데 이것을 쉘 알고리즘이라고 부른다.

기수 정렬 알고리즘은 버킷을 이용한다. 정렬할 원소를 버킷에 차곡차곡 넣는 과정을 반복해 정렬한다.

예를 들어 위와 같은 숫자를 정렬한다고 생각해보자.

처음에는 이렇게 10개의 버킷을 준비한다. 

먼저 1의 자릿수에 따라서 각각의 숫자를 버킷에 정렬한다.

이제 버킷에 있는 숫자를 다리 순서대로 정리한다. 그럼 0에서 온 것, 1에서 온것...9에서 온 것 이렇게 쭉 정렬이 된다.

이제 십의 자릿수 대로 정렬을 해서 버킷에 넣는다.

다시 차례대로 정렬하면 정렬이 완벽하게 된다. 

이런 정렬 알고리즘들의 성질은 4가지가 있다.

1. adaptive

부분적으로 이미 정렬된 데이터를 받았을 때 더 좋은 성능을 보이는가?

ex) 버블 정렬: 1 2 3 4 5를 정렬하는 것이 5 4 3 2 1을 정렬하는 것보다 성능이 더 좋다.

2. stable

같은 값을 갖는 원소들이 자리를 바꾸는가?

ex) 1 2 2 4 5를 정렬할 때 2끼리 자리를 바꾸면 stable 하지 않다고 말한다.

3. in-place

추가적으로 요구하는 메모리의 개수가 상수 개 즉, O(1)인가?

ex) 대부분의 정렬 알고리즘은 메모리를 추가적으로 요구하지 않지만, 분할 정복 알고리즘의 경우는 실제 시스템 스택을 상당히 많이 요구하기 떄문에 in-place라고 말하기 힘든 경우가 발생한다.

4. online

데이터가 계속 증가해도 정렬이 가능한가?

ex) 합병 정렬은 주어진 데이터를 반으로 쪼개나가는 방식이기 때문에 추가 데이터가 들어오면 다시 정렬하기 쉽지 않다. 삽입 정렬이라면 데이터가 더 들어와도 적당한 위치에 삽입을 하면 되기 때문에 online의 성질이 있다고 할 수 있다.

결론적으로 단순 정렬 알고리즘은 O(n²), 분할 정복 정렬 알고리즘은 O(n log n)의 성능을 보인다. 실제로 성능의 차이가 크기 때문에 가능하면 분할 정복에 기반한 알고리즘을 사용할 것을 권장한다.