[C] Quicksort:: 퀵정렬

안녕하세요. 우주신 입니다.

오늘은 퀵정렬(Quick Sort)에 대해 포스팅 하겠습니다.

퀵정렬은 시간복잡도가 O(nlogn)으로 실제로 매우 효율적인 알고리즘이라 자주 사용된다.

우선, 위키피디아의 퀵정렬 정의를 참고해보자.

퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다.

1. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗(Pivot)이라고 한다.
2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
3. 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.

재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

그림을 보며 1번, 2번 과정인 분할을 따라가보자.

1. 먼저 피벗(pivot)을 고른다. 여기서는 첫번째 인덱스인 6이 피벗이다.

피벗 자리에 i를 그리고 i 바로 뒤에 j를 초기화 한다.

2. 피벗을 기준으로 앞에는 피벗보다 값이 작은 모든 원소들로, 뒤에는 피벗보다 값이 큰 원소들로 나누자.

원리는 매우 단순하다. j를 1씩 증가시키며 j의 자리에 있는 값이 피벗 값보다 크면 아무 조치를 하지 않고 

j의 자리에 있는 값이 피벗 값보다 작으면 i를 1 증가 시키고 swap 한다.

j 자리의 10은 피벗 값인 6보다 크므로 아무것도 하지 않고 j를 바로 다음 칸으로 옮긴다.

13 또한 피벗 값인 6보다 크므로 j를 다음 칸으로 옮긴다.

이번에는 j 자리의 5가 피벗 값인 6보다 작다. 

이 때, i를 1 증가시키고, j의 자리의 값과 Swap 한다.

밑의 그림처럼 5와 10이 Swap된 것을 알 수 있다.

j를 다음칸으로 이동한다. 8은 피벗 값보다 크므로 아무 것도 하지 않는다.

j를 다음 칸으로 이동한다. 3은 피벗 값보다 작다.

그러므로 i를 1 증가 시킨 후, j의 자리에 있는 3과 i의 자리에 있는 13을 Swap 한다. 

또 다시 j를 다음 칸으로 이동한다.

이번에도 마찬가지로 j의 자리에 있는 2는 피벗 값보다 작으므로 

i를 다음 칸으로 이동 시킨 후와 j의 자리에 있는 2와 i의 자리에 있는 10을 서로 Swap한다.

j를 다음 칸으로 이동한다. 11은 피벗 값보다 크므로 아무 것도 안한다.

j를 다음 칸으로 이동 시켰을 때 배열의 끝이면, i의 자리에 있는 값과 피벗의 값을 Swap 한다.

즉, 피벗인 6과 i의 자리에 있는 2와 Swap 한다.

여기까지가 위 위키피디아 정의에서 설명한 1번과 2번의 과정이다.

이제 3번에서 설명한 것처럼 피벗을 기준으로 분할된 두 개의 리스트를 재귀적으로 1번, 2번 과정을 반복하면 된다.

위 예시에서는 [2, 5, 3]과 [8, 13, 10, 11]의 리스트에서 위와 같이 분할을 하고 

거기서 나눠지는 각각의 리스트들을 대상으로 리스트의 길이가 1이 될 때까지 

분할 과정을 반복하면 정렬이 완성되는 것을 확인할 수 있다. 

코드를 보며 복습해보자.

38:: 인자로 배열 arr과 배열의 시작, 끝 인덱스인 start, end를 받는다.

40:: 피벗의 자리인 p를 선언한다.

43:: 배열의 크기가 1일 때는 멈춰야 한다.

45:: 배열을 분할하고 (1번 2번 과정), 분할이 완성된 후의 피벗을 p에 저장한다.

47:: 피벗을 기준으로 왼쪽 배열을 재귀적으로 퀵정렬 한다. (3번 과정)

48:: 피벗을 기준으로 오른쪽 배열을 재귀적으로 퀵정렬 한다. (3번 과정)

1번과 2번의 분할에 대한 코드이다.

 

13:: 인자로 배열 arr와 start, end 인덱스를 받는다.

15:: 배열의 첫번째 자리의 값을 pivot 변수에 저장한다.

16:: 그리고 i를 첫번째 자리인 start로 초기화 한다.

19:: j를 i+1로 초기화하고 j를 1씩 증가시키며 배열의 끝인 end 자리까지 반복한다.

21:: j 자리의 값이 피벗의 값보다 작다면 i를 다음 칸으로 이동한 후 Swap 한다.

26:: j가 마지막 인덱스까지 이동한 후, 반복문을 나온 뒤 i의 자리의 값과 피벗의 값을 Swap 한다.

27:: pivot의 자리를 반환한다.

다음 시간에는 퀵정렬의 최악의 경우를 방지하기 위한 Randomized Quicksort에 대해 정리해보겠습니다.

고생하셨습니다~

끝

# 참고 # 

 - "Introduction to Algorithm" Cormen, Charles, Ronald, Clifford

- 한양대학교, 정형수 교수님, 알고리즘 수업