[알고리즘/정렬] 2. 퀵 정렬(Quick Sort)
01. 퀵 정렬 개념
1) 퀵 정렬 과정
-
step1 : pivot의 위치를 선정(그림에서는 맨 왼쪽)
-
step2 : low는 pivot보다 큰 숫자가 나올 때까지 오른쪽으로 이동하고, high는 pivot보다 작은 숫자가 나올 때까지 왼쪽으로 이동한다.
-
step3 : low와 high pointer가 멈추면 서로 교환해준다. low와 high pointer를 다시 이동시켜 준다.
-
step4 : low와 high가 엇갈릴 때까지 같은 조건으로 low와 high pointer를 이동한다.
-
step5 : pointer의 이동을 멈추고 pivot과 high를 교환한다.
-
step6 : pivot을 기준으로 왼쪽에는 작은 숫자들, 오른쪽에는 큰 숫자들이 위치하며 나눠진다. 현재의 pivot에 해당하는 숫자는 자리가 고정된다.
-
step7 : 이후에는 왼쪽 숫자들과 오른쪽 숫자들의 pivot을 선정하여 재귀적으로 step1~6를 반복한다.
2) 퀵 정렬 개념
- 분할(Divide) : 입력 배열을 pivot을 기준으로 비균등하게 2개의 부분 리스트로 분할한다.
- pivot의 왼쪽에는 pivot보다 작은 숫자 배열, 오른쪽에는 pivot보다 큰 숫자 배열이 위치한다.
- 정복(Conquer) : 부분 배열을 quick sort를 재귀적으로 사용해 정렬한다.
- 재귀적으로 quick sort를 사용하는 과정에서 divide가 된다.
02. 퀵 정렬 코드(Python)🔍
# 💡퀵 정렬
# 2. 분할해서 pivot 기준으로 pivot보다 작은 것은 왼쪽으로, pivot보다 큰 것은 오른쪽으로 넣기
def partition(start, end):
# 2-1. pivot 지정 - 왼쪽 끝으로 지정
pivot = quick_nums[start]
low = start + 1
high = end
# 2-2. low high 엇갈릴 때까지 반복
while True: # low와 high가 엇갈려 있지 않고,
while low <= high and quick_nums[low] <= pivot: # 각 세부 반복문을 돌면서 low는 pivot보다 큰 수가 나올 때까지 오른쪽으로 이동
low += 1
while low <= high and quick_nums[high] >= pivot: # high는 pivot보다 작은 수가 나올 때까지 왼쪽으로 이동
high -= 1
# 📌 low == high 이유: 엇갈리는 순간을 만들기 위해,
# 📌 quick_nums[low] == pivot 허용한 이유: pivot과 동일한 것들이, low, high로 의미없이 서로 교환되는 것을 막기 위해
# 2-3. 세부 while 문이 멈추고, 엇갈려 있다면 바깥 while을 빠져 나오고
if low > high:
break
# 엇갈려 있지 않으면 low와 high를 서로 교환해준다. -> 엇갈린 상황에서 low high를 교환해주면 정렬을 한 것들이 망가진다.(10 22 -> 22 10)
else:
quick_nums[low], quick_nums[high] = quick_nums[high], quick_nums[low]
# 2-4. 엇갈린 상태에서 pivot 값과 high 값을 교환(엇갈려 있으므로 high가 low보다 작다 -> high를 pivot과 바꾼다.)
quick_nums[start], quick_nums[high] = quick_nums[high], quick_nums[start]
# 2-5. 새로운 pivot의 위치를 반환 -> 이 숫자의 위치는 영구적으로 고정
return high
# 1. start와 end 사이를 정렬하기
def quick_sort(start, end):
# 1-1. start와 end가 엇갈리지 않을 때 sort 가능
# start와 end가 같아도 되지만 어차피 partition 후에 pivot = start = end이 되므로 그 아래 코드에서 걸러진다.)
if start < end:
pivot = partition(start, end)
quick_sort(start, pivot-1) # pivot보다 작은 것들을 sort,
quick_sort(pivot+1, end) # pivot보다 큰 것들을 sort
quick_nums = [0, 55, 22, 33, 2, 1, 10, 26, 42]
quick_sort(0, len(quick_nums)-1)
print(quick_nums) # [0, 1, 2, 10, 22, 26, 33, 42, 55]
- pivot을 기준으로 왼쪽 부분 리스트와 오른쪽 부분 리스트를 재귀적으로 quick sort하면서 각각의 pivot들을 고정시켜준다.
03. 퀵 정렬 시간복잡도⏱
1) 최선의 시간복잡도 : O(nlogn)
-
각 순환 호출 전 단계에서의 비교 연산(평균): n
- pivot을 기준으로 왼쪽 오른쪽을 나누어 각각을 quick sort로 순환 호출하기 전에 비교 연산을 통해 pivot의 위치를 지정하는 연산
-
순환 호출 : logn
- merge sort처럼 쪼갤 때마다 두 부분으로 나눌 수 있으면 재귀의 깊이는 logn이다.(최적의 상황)
- T(n) = n + 2T(n/2)
- n : 재귀 전에 pivot 선정해서 왼쪽 오른쪽 나누기
- 2T(n/2) : 왼쪽, 오른쪽 두 부분 리스트에서 quick sort 호출하기
- T(n) = O(nlogn)
2) 최악의 시간복잡도 : O(n^2)
-
이미 정렬된 형태에서 최악의 시간 복잡도를 갖는다.
-
정렬을 진행하면, pivot이 한 쪽 끝으로 쏠리게 되서 두 부분 리스트를 나눌 수가 없다.
- 순환 호출이 각 단계마다 한번씩만 일어난다. 순환 호출 단계는 n이 된다.
- 호출 전, 각 숫자들을 pivot과 비교하는 연산은 평균적으로 n이다.
-
순환 호출 단계 * 호출 전 단계에서의 비교 연산 : O(n^2)
-
결국 퀵 정렬의 최악의 시간복잡도는 버블 정렬과 비슷한 원리다.
04. 퀵 정렬 특징❗
-
분할 정복 알고리즘의 한 종류
- 분할 정복이란 문제를 작은 2개의 문제로 분리하고, 각각을 해결한 다음, 그 결과를 모아서 원래의 문제를 해결하는 전략
- merge sort와는 다르게 불균형 분할이다.
-
pivot을 선정하는 방법에 따라 속도가 달라진다.
-
이미 정렬되어 있거나, 역순으로 정렬되어 있는 배열에서는 O(n^2)로 매우 느리다.
-
배열 안에서 교환이 일어나므로 merge sort와는 달리 추가 메모리를 필요로 하지 않는다.
-
시간 복잡도가 O(nlogn)을 가지는 다른 정렬 알고리즘(merge sort, heat sort)와 비교했을 때, 가장 빠르다.
- 한번 결정된 pivot들은 고정되어 다음 연산에 포함되지 않기 때문이다.
Author And Source
이 문제에 관하여([알고리즘/정렬] 2. 퀵 정렬(Quick Sort)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kongji47/알고리즘정렬-2.-퀵-정렬Quick-Sort저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)