Quick Sort?
분할 정복 방법을 통해 주어진 배열을 정렬하는 알고리즘.
분할정복 : 문제를 작은 2개의 문제로 분리하고 각각 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략
아래의 배열을 기준으로 설명하면,
[6, 5, 1, 4, 7, 2, 3]1. 피벗이라는 임의의 기준값을 설정한다.
피벗 = 4
arr = [6, 5, 1, 4, 7, 2, 3]2. 다음과 같이 pivot 값을 기준으로 pivot 보다 작은 값의 그룹과, pivot보다 큰 값의 그룹으로 나눈다(분할)
[3, 2, 1] < 4 < [7, 5, 6]위와 같이 pivot 값보다 작은 값들을 모두 왼편으로 몰고, 큰 값들은 모두 오른편으로 몰면 기준값은 정확히 정렬된 위치에 놓이게 된다.
또한 이렇게 분할을 해놓으면 앞으로 더 이상 왼편과 오른편의 값들 간에는 비교를 할 필요가 없음.
3. 왼쪽부터 정렬, pivot = 2
[3, 2, 1] => [1] < pivot < [3]
result => [1, 2, 3]4. 오른쪽도 동일한 방식으로 정렬.
pivot = 5
[7, 5, 6]
# 5보다 작은 값은 없으므로, 7과 6을 모두 오른편에 위치시킨다
[5] < [7, 6]
# 그 후 오른쪽에 2개의 값이 있기 때문에 추가 정렬이 필요하다. 동일한 방식의 정렬을 적용.
pivot = 7
[6] < 7 < []
5. 마지막으로 좌우로 분할된 값들을 모두 합치면 다음과 같이 정렬된 배열을 얻을 수 있다.
[1, 2, 3, 4, 5, 6, 7]결과적으로 pivot값을 기준으로 더 작은 값과 큰 값으로 반복적으로 분할하여 정렬해나가는 방식.
특징
- 병합정렬과 퀵 정렬은 분할정복과 재귀 알고리즘을 사용한다는 측면에서는 유사하지만, 내부적으로 정렬을 하는 방식에서는 큰 차이가 존재한다.
- 병합 정렬은 항상 정 중앙을 기준으로 단순 분할 후 병합 시점에서 값의 비교 연산이 이루어진다.
- 퀵 정렬은 분할 시점부터 비교 연산이 일어나기 때문에 그 이후 병합에 들어가는 비용이 매우 적거나 구현 방법에 따라서 아예 병합을 하지 않을 수 도 있다.
복잡도
- 퀵 정렬의 성능은 pivot 값을 어떻게 선택하느냐에 따라 크게 달라질 수 있따.
- 이상적인 경우, O(log(n))의 시간 복잡도를 가진다.
하지만, pivot 값을 기준으로 분할할때, 값들이 한편으로 크게 치우치게 되면 성능이 저하되며, 최악의 경우 한편으로만 모든 값이 몰리게 되어 O(n^2)의 시간복잡도를 가진다.- 따라서 상용코드에서는 중앙값에 가까운 pivot값을 선택할 수 있는 전략이 요구되며 배열의 첫 값과 중앙값, 마지막 값 중에 크기가 중간인 값을 사용하는 방법이 많이 사용된다.
- 퀵 정렬의 공간 복잡도는 구현 방법에 따라 달라질 수 있는데, in-place sorting 방식으로 구현할 경우, O(log(n))의 공간 복잡도를 가진다.
구현
# Process
# 1. 배열 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
# 2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 배열을 둘로 나눈다.
# 이렇게 배열을 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
# 3. 분할된 두 개의 작은 배열에 대해 재귀적으로 이 과정을 반복한다.
def quickSort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
lesser_arr, equal_err, greater_arr = [], [], []
for num in arr:
if num < pivot:
lesser_arr.append(num)
elif num > pivot:
greater_arr.append(num)
else:
equal_err.append(num)
return quickSort(lesser_arr) + equal_err + quickSort(greater_arr)
arr = [7, 6, 3, 1, 1, 3, 5, 4]
print(quickSort(arr))
# [1, 1, 3, 3, 4, 5, 6, 7]
persistently