정렬 알고리즘 : 퀵 정렬

1. 퀵 정렬 : 이해와 구현

퀵 정렬도 분할 정복에 근거하여 만들어진 정렬 방법입니다. 실제로 퀵 정렬 역시 정렬대상을 반씩 줄여나가는 과정을 포함합니다. 오름차순 정렬을 기준으로 설명 드리겠습니다.

 

큰 흐름을 보자면 퀵 정렬은 피벗이라는 기준점을 가지고 시작을 합니다. 피벗을 기준으로 피벗보다 작은 값은 왼쪽으로, 큰 값을 오른쪽으로 세팅을 합니다. 이 과정을 재귀적으로 처리하면 퀵 정렬은 끝나게 됩니다. 그림을 통해서 자세히 설명 드리겠습니다.

1단계 : 초기화

left : 정렬 대상의 가장 왼쪽 지점을 가리키는 이름

right : 정렬 대상의 가장 오른쪽 지점을 가리키는 이름

pivot : 피벗이라 발음하고 중심점, 중심축의 의미를 담고 있다.

low : 피벗을 제외한 가장 왼쪽에 위치한 지점을 가리키는 이름

high : 피벗을 제외한 가장 오른쪽에 위치한 지점을 가리키는 이름

 

크게 보면 이렇게 변수를 선언하였습니다. 여기서 알아야 할 것은 피벗은 기준이 되는 기준점을 뜻하게 되는데 저는 가장 왼쪽 값을 피벗으로 결정하였고 물론 다르게 결정 할 수도 있습니다.

2단계 : low와 high 이동

 low의 오른쪽 방향 이동 : 피벗보다 큰 값을 만날 때 까지

 high의 왼쪽 방향 이동 : 피벗보다 작은 값을 만날 때 까지

 

여기서 주의해야 할 점은 high와 low는 같이 움직이는게 아니라 별개로 독립적으로 움직입니다.

3단계 : low와 high의 교환

low가 우측으로 이동하다가 7을 만나면 멈추게 됩니다. 그리고 high도 좌측으로 이동하다가 4를 만나면 멈추게 됩니다. 그럼 이 값들을 교환해줍니다.

교환 후 이동을 계속, 그리고 또 교환합니다.

이동을 계속, high와 low가 역전 될 때 까지합니다.

low와 high가 역전되면 교환을 진행을 마무리 합니다.

4단계 : 피벗의 이동

high와 low가 역전되면, 피벗과 high의 데이터 교환

그럼 5를 기준으로 좌측에는 5보다 작은 값, 우측은 큰 값으로 세팅이 되었습니다.

재귀적으로 두 개의 영역으로 나누어 똑같은 과정을 거칩니다.

left와 right가 left>right 일 때 까지 반복합니다.

퀵 정렬의 과정은 다음과 같고 이제 코드레벨에서 다시 한번 살펴보겠습니다.

 

정렬되지 않은 크기가 7인 배열이 있습니다. QuickSort 함수에 이 배열의 주소와 인덱스0과 인덱스 6의 값을 매개변수로 전달합니다.

QuickSort 함수를 살펴보겠습니다. 배열의 주소, 인덱스 0 = left 인덱스 6= right로 전달됩니다. 조건문의 의미가 뭔지 아시겠나요? left right는 사실 움직이는 것이 아닙니다. 피벗이 결정되고 정렬이 1회 완료되고 또다시 피벗이 결정되고 정렬이 진행될수록 left와 right의 거리는 점점 좁아집니다. 즉 left와 right가 각각 정렬대상의 시작과 끝을 의미하므로 두 개의 값이 교차될 때는 더 이상 정렬할 대상이 없다는 의미가 됩니다.

 

어쨌든 해당 조건에 만족하면 조건문안으로 들어와서 Partition 함수가 호출됩니다. 

Partition 함수가 호출되고 아까

이 그림에서 피벗이 교환되어 찾아간 위치 값을 반환합니다. 그럼 이 위치 값을 pivot 변수에 저장하고 이 pivot 위치값을 기준으로 좌우를 똑같이 정렬해줍니다.

 

이 그림처럼 말이죠 

퀵 정렬을 재귀의 성격을 가진다고 했습니다. pivot을 기준으로 나눠진 좌측은 QuickSort(arr, left, pivot - 1); 함수를 호출하고 우측은 QuickSort(arr, pivot + 1, right); 이 함수를 호출합니다.

이제 Patition 함수에 대해서 자세히 살펴보겠습니다.

가장 좌측 값을 피벗으로 세팅하고 left 바로 우측을 low로 세팅합니다. 그리고 맨 우측값을 high라고 세팅합니다.

 

low와 high가 교차되지 않을 때 까지 반복합니다.

 

low가 우측으로 이동하기 위해선 피벗보다 큰 값을 만나는 때입니다. 따라서 피벗이 low가 가리키는 값 보다 같거나 클 때, 또한 low값이 right을 넘어가기 전까지 low는 우측으로 이동합니다.

 

이와 마찬가지로 high가 좌측으로 이동하기 위해서는 피벗이 가리키는 값보다 작은 값을 만날 때까지 이동하고 또한 좌측으로 이동할 때 피벗은 검사의 대상에서 제외해야 하기 때문에 high+1로 세팅을 해줍니다.

 

이러한 과정이 끝나면

low와 high가 저렇게 이동을 하게 됩니다. (예를 들어서 말하는 겁니다). 그럼 이제 두 값을 교환해야 겠지요?

 

교환의 과정은 Swap함수를 통해서 이뤄집니다.

 

하지만 교환을 하기 전에 low와 high가 교차되는 지를 확인해야 합니다. 만약 교차되었으면, low와 high의 이동 및 교환의 과정이 완료되었음을 의미하기 때문입니다. 교차가 안되었으면 두 값을 스왑 합니다.

 

만약 low와 high의 값이 교차가 되면 피벗과 high가 가리키는 대상을 교환합니다.

 

그 후에 옮겨진 피벗의 위치정보를 반환합니다.

2. 퀵 정렬 : 성능 평가

 위 그림에서 보이듯이 피벗이 결정이 되면 low는 오른쪽으로 high는 왼쪽으로 이동을 시작합니다. 그리고 그 이동은 low와 high가 역전될 때 까지 진행됩니다. 

그런데 이동의 과정에서 피벗과의 비교를 매번 수반하므로, 하나의 피벗이 제 자리를 찾아가는 과정에서 발생하는 비교연산의 횟수는, 데이터의 수에 해당하는 n이라 할 수 있습니다.

물론 피벗으로 인해서 n보다 하나 적은 수의 비교연산이 이뤄지지만 이는 무시할 수 있습니다.

 

최선의 경우

사실 퀵정렬에서 피벗을 값들의 중간 값으로 선택하는 것이 가장 좋은 최선의 경우입니다. 최선의 경우라고 가정할 때 모든 데이터가 피벗과 데이터 비교를 합니다.

 

5를 기준으로 하나씩 다 말이죠, 사실 정확히 말하자면 n-1이라고 볼수도 있지만 빅오를 따지는 것이기 때문에 n이라고 가정하겠습니다.

 

그리고 만약 8개의 데이터가 있고 중간값이 피벗으로 선택되면

8개

4개

2개

1개

이렇게 총 3회에 거쳐서 데이터가 둘로 나눠집니다.

n개의 데이터가 1개로 나눠지려면 log(2)n로 표현할 수 있습니다.

따라서 둘로 나뉘는 횟수는 log(2)n가 되고 나눠질 때 마다 각각 n번씩 피벗과 비교연산을 하게됨으로 최선의 경우 빅오는 nlog(2)n이 됩니다.

 

최악의 경우.

만약 숫자들이 이렇게 정렬되어 있고 값들 중 가장 작은 값을 피벗으로 선택하게 되면 둘로 나뉘는 횟수는 약 n번이 됩니다. 사실 나뉘어 지는 것이 아니라 n차에 걸쳐서 피벗의 선택과정이 일어나게 됩니다. 

그리고 매 단계별 피벗보다 작은 값을 만날 때까지 low가 움직여야 하는데 작은 값이 하나도 없으므로 쭉쭉 이동하게 되고 high도 마찬가지입니다.

그러므로 매 단계별 비교 연산의 횟수는 약 n회를 거치게 되고

 

따라서 최종적으로 최악의 경우 빅오는 O(n^2)를 가지게 됩니다.

사실 퀵 정렬은 예외적으로 최악의 경우를 고려하지 않아도 됩니다. 왜냐하면 조금만 노력해도 중간에 가까운 값으로 빅오를 선택하기만 하면 최악의 경우는 일어나지 않기 때문입니다. 

따라서 퀵 정렬의 성능은 최선의 경우를 근거로 따지게 됩니다.