Quick Sort Algorithm

Quick Sort

최악의 경우 실행시간은 $O(n^2)$이다.

평균적으로, 실행시간은 $O(n\lg{n})$이다. 이때의 숨겨진 상수 계수는 다른 알고리즘보다 작아서, 실제로는 매우 빠르게 동작하는 편이다.

퀵 정렬

 

퀵 정렬은 분할-정복 방식으로 작동한다.

• 분할: 배열 A[q...r]을 피벗을 기준으로 두 개의 부분 배열로 나눈다. 앞 부분의 배열 A[p...q-1]의 모든 요소는 피벗 A[q] 보다 작거나 같고, 뒷 부분의 배열 A[q+1...r]의 모든 요소는 피벗 A[q]보다 크거나 같다.
• 정복: 분할된 두 부분 배열을 재귀 호출을 통해 각각 정렬한다.
• 결합: 퀵 정렬은 제자리 정렬이기 때문에, 두 부분 배열을 따로 결합할 필요는 없다.

분할 과정은 PARTITION 이라는 절차를 이용해 이루어지며, 이 절차는 피벗을 선택하고, 피벗을 기준으로 배열을 분할한 후 피벗의 최종 위치인 q를 반환한다.

---

Partitioning

파티션

 

파티션 절차에서는 서브 배열 A[p...r]에서 마지막 요소 A[r]을 피벗으로 설정한다.

i의 초기값은 p-1이며, j의 초기값은 p가 된다. j의 값이 r-1이 될 때까지 반복한다.

만약에 A[j]의 값이 피벗보다 작거나 같으면, i값을 하나 증가시키고, A[j]와 A[i]의 값을 교환한다.

이 과정을 통해 피벗보다 작거나 같은 값의 요소들이 앞쪽 배열로 모이게 된다.

비교하고 교환하는 과정이 끝나면, 피벗 값과 A[i+1]의 값을 교환하고, i+1의 값을 반환(피벗이 있는 인덱스)한다.

 

이 알고리즘이 진행되는 동안 배열은 네 개의 영역으로 나뉜다.

A[p...i] = 피벗보다 작은 부분

A[i+1 ... j-1] = 피벗보다 큰 부분

A[j ... r-1] = 아직 처리되지 않은 부분

A[r] = 피벗

파티션 과정

---

반복 불변 조건을 사용한 Partition 알고리즘의 정확성

 

파티션 알고리즘의 반복 불변 조건엔 세가지가 있다.

배열 A[p...i]의 모든 요소는 피벗보다 작거나 같으며, 배열 A[i+1...j-1]의 모든 요소는 피벗보다 크다는 것과, A[r]은 피벗이라는 것이다.

 

• Initializaion(초기화): 반복문이 시작하기 전, 배열 A[p...i]와 A[i+1...j-1]는 아직 비어있고, 피벗은 배열의 마지막 원소에 위치해 있다. 즉, 이시점에서는 분할이 이루어지지 않았기에 불변 조건이 자동으로 만족된다.
• Maintenance(유지): 반복문이 실행될 때, A[j]가 피벗보다 작거나 같으면 A[j]와 A[i+1]을 교환하고 i와 j를 모두 증가시킨다. 이때 작은 값들이 왼쪽 부분 배열에 모이면서 불변 조건이 유지된다. A[j]가 크면 교환하지 않고 j값만 증가시킨다. 이때 큰 값들이 오른쪽 부분배열에 모이게 된다. 
• Termination(종료): 반복문이 종료된 후, j=r이 되어 배열의 모든 원소가 피벗을 기준으로 분할된다.
• 마지막으로 피벗 A[r]과 A[i+1]을 교환하여 피벗이 올바른 위치에 자리잡도록 한다.

PARTITION은 배열의 각 원소에 대해 한번씩만 비교 및 교환을 수행하기 때문에 시간 복잡도가 $\Theta(n)$이 된다.

---

Quick Sort의 시간복잡도

 

퀵 정렬의 실행 시간은 부분 배열의 분할 방식에 따라 달라진다.

 

최악의 경우는 부분 배열이 완전히 불균형적으로 나뉠 때 발생한다.

한쪽 부분 배열에 원소가 0개 있고, 다른 한쪽 부분 배열에 n-1개의 원소가 있을 때를 말한다. 피벗의 값이 배열에서 가장 큰 값이거나 가장 작은 값일 때 배열이 완전히 불균형적으로 나뉜다.

이 경우 재귀 관계식은 $T(n) = T(n-1) + T(0) + \Theta(n) = T(n-1) + \Theta(n) = \Theta(n^2)$이 된다.

퀵 정렬의 최악의 경우 시간 복잡도는 삽입 정렬과 동일하게 $O(n^2)$이지만, 사실 퀵 정렬의 최악의 경우는 정렬된 배열을 입력으로 받았을 때 발생한다. 반면 삽입 정렬은 정렬된 배열을 입력으로 받으면 $O(n)$의 시간복잡도를 가진다.

 

최선의 경우는 매번 부분 배열이 균형적으로 나뉠 때 발생한다.

이때, 각 분할에서 두 부분 배열의 크기는 최대 n/2 이하가 된다.

이 경우 재귀 관계식은 $T(n) = 2T(n/2) + \Theta(n) = \Theta(n\lg{n})$이 된다.

 

퀵 정렬의 평균 실행 시간은 최선의 경우에 더 가깝다.

만약 PARTITION이 항상 9:1로 배열을 나눈다고 가정하면, $T(n) \leq T(9n/10) + T(n/10) + \Theta(n)$이 되는데, 이 재귀식의 시간 복잡도는 역시 $O(n\lg{n})$이다. 즉, 배열이 완벽하게 균형이 잡히지 않더라도 비율이 일정하게 유지되면 퀵 정렬의 평균 실행 시간은 $O(n\lg{n})$이 되는 것이다. 이는 배열을 어떤 상수 비율로 나누든, 재귀 트리의 깊이는 $O(\log{n})$이 된다는 의미이다. 

 

재귀 트리에서 분할은 항상 일정하지 않고, 좋은 분할과 나쁜 분할이 섞여도 점근적 실행 시간에는 영향이 없다.

따라서 최악의 경우는 배열이 매 단계에서 불균형하게 분할될 때만 발생한다.

---

Randomized version of QuickSort

 

일반적인 퀵 정렬은 모든 입력 배열이 무작위로 주어질 것이라고 가정하지만, 실제로는 그렇지 않을 수 있다.

정렬된 배열이 입력되면 최악의 경우가 되어버리니 사전에 방지해야한다. 이를 위해 퀵 정렬에 랜덤화를 추가한 것이다.

 

랜덤화된 알고리즘은 입력 배열이 특정한 순서로 주어져도 성능을 보장할 수 있다.

랜덤화 파티션

 

피벗을 항상 배열의 마지막 원소로 선택하지 않고, 서브배열에서 무작위로 고른 하나의 원소를 피벗으로 설정한다.

이렇게 랜덤으로 피벗을 설정하게 되면, 평균적으로 균형잡힌 분할을 유도할 수 있다.

랜덤화 퀵 정렬

 

랜덤화된 퀵 정렬 알고리즘을 사용하면, 이미 정렬된 배열을 입력으로 받았어도 피벗이 랜덤하게 설정되기 때문에, 최악의 경우는 피할 수 있게된다.

---

여기까지가 알고리즘 수업의 중간고사 범위이다.

공휴일이 많이 겹쳐서 내용이 조금 적어졌기에, 수월하게 공부할 수 있을거라 믿는다.

다들 시험 화이팅팅

 

** 대학교 수업을 듣고 이해한 부분을 최대한 풀어서 작성한 글입니다.

틀린 정보가 존재할 수 있으며, 언제나 피드백은 환영입니다. **