정렬 알고리즘(Sorting Algorithm)의 모든 것 ③ - 퀵 정렬(Quick Sort)

정렬 알고리즘의 세 번째 이야기, 퀵 정렬(Quick Sort)

3. 정렬 알고리즘(Sorting Algorithm)의 모든 것 ③ - 퀵 정렬(Quick Sort)

 : 퀵 정렬은 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 퀵 정렬은 분할 정복 방법을 통해 리스트를 정한다.

1. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 '피벗'이라고 한다.

2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.

3. 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.

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

(출처 - 위키백과)

한 마디로, 피봇을 정하여 피봇을 기준으로 큰 수, 작은 수를 정렬해 간다.

<< 퀵 정렬 c++ 기준 코드 >>

* 보통 첫 피봇은 첫 번째 원소로 한다.

* 정렬되지 않은 크기가 7인 배열 A가 있다고 하자

-> A = [5 - 9 - 3 - 8 - 1 - 4 - 2]

0. 위의 코드 대로 첫 피벗을 5로 삼고 이를 p라고 하자.

-> A = [5 - 9 - 3 - 8 - 1 - 4 - 2]

  p list[i]                  list[j]

-> p = 5, i = 1, j = 6, list[i] = 9, list[j] = 2

1-1. 리스트 왼쪽에 있는 i 위치의 값이 피벗 값보다 크고, 오른쪽에 있는 j 위치의 값은 피벗 값보다 작으므로 둘을 교환한다.

-> A = [5 - 2 - 3 - 8 - 1 - 4 - 9]

-> p = 5

1-2. list[1]은 p=5보다 작으므로 i++, list[6]은 p=5보다 크므로 j--

-> i = 2, j = 5

2-1. j위치의 값이 피벗 값보다 작지만, i 위치의 값이 피벗값보다 작으므로 교환이 일어나지 않는다.

-> A = [5 - 2 - 3 - 8 - 1 - 4 - 9]

  p       i              j 

2-2. list[2]는 p보다 작으니 i++, list[5]는 p보다 작으므로 j는 그대로 둔다.

-> i = 3, j = 5

3-1. i 위치를 피벗 값보다 큰 값이 나올 때 까지 진행하여 j위치의 값과 교환한다.

-> A = [5 - 2 - 3 - 8 - 1 - 4 - 9]

      p             i         j

-> A = [5 - 2 - 3 - 4 - 1 - 8 - 9]

-> p = 5

3-2. list[3]은 p보다 작으므로 i++, list[5]는 p보다 크므로 j--

-> i = 4, j = 4

4. i와 j가 동일 / list[4]는 p보다 작으므로 i++

-> i = 5, j = 4

5. i 위치가 j위치보다 커지면, i위치의 값과 피벗 값을 교환한다.

-> A = [1 - 2 - 3 - 4 - 5 - 8 - 9]

  p

6. 피벗 값 좌우의 리스트에 대해 각각 퀵 정렬을 재귀적으로 수행한다.

-> 1 - 2 - 3 - 4         5 - 8 - 9

7. 완성된 리스트

-> 1 - 2 - 3 - 4 - 5 - 8 - 9

<< 퀵 정렬 장, 단점 >>

** 장점

- 속도가 빠르다.

- 메모리가 크게 낭비되지 않는다.

** 단점

- 정렬된 리스트에 대해서는 퀵 정렬이 오히려 성능 저하가 있을 수 있다.

<< 퀵 정렬 시간 복잡도 >>

** 평균 : O(nlogN)

** 최악(어느정도 정렬된 리스트 등) : O(N^2)