퀵 정렬(Quick Sort)

Goal

- Quick Sort 에 대해 설명할 수 있다.

- Quick Sort 과정에 대해 설명할 수 있다.

- Quick Sort를 구현할 수 있다.

- Quick Sort의 시간 복잡도를 계산 할 수 있다.

1. Quick Sort Summary

'특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눔'

2. Quick Sort Process

- 배열 가장 왼쪽 원소를 고른다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다. (key 값)

- 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기 준으로 배열을 둘로 나눈다. 이렇게 배열을 둘로 나누는 것을 분할(Divide) 이라고 한다.

- 하나의 피벗이 자리를 잡고 더이상 움직이지 않는다.

- 분할된 두 개의 작은 배열에 대해 재귀(Recursion)적으로 이 과정을 반복한다.

3. Quick Sort Coding

4. Quick Sort 시간 복잡도

장점

- 대표적인 '분할 정복' 알고리즘으로 평균 속도가 O(N * logN)이다.

O(N^2)

ex) 1 2 3 4 5 6 7 8 9 10

=> N ^ 2 = 10 * 10 = 100

O(N * logN)

ex) 1 2 3 4 5 = 5 * 5 = 25

+) 1 2 3 4 5 = 5 * 5 = 25 = 50 => O(N^2)와 비교해서 상당히 빠르다

- 삽입정렬, 버블정렬, 선택정렬 보다 빠르다.

단점

- 최악 시간 복잡도는 O(N^2) 이다. (이미 충분히 정렬되어있을경우)

1Sang