최근에 퀵 정렬에 대해 공부했다.
이것이 코딩 테스트다 책을 보면서 앞서 보여준 선택 정렬, 삽입 정렬 을 보다가 퀵 정렬을 보았을땐... 정말이지...
그래도 학부생 때 배웠던 기억을 더듬어 가며 개념을 바로잡고자 같은 코드도 몇번 씩 보며 작성해 보았고 마참내 이해하는데 성공했다.
1. 퀵 정렬
퀵정렬의 개요는 다음과 같다.
기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다.이처럼 하나의 기준을 정하고 그 기준보다 작은 수와 큰 수를 교환하고 리스트를 반으로 나누어 교환을 이어나가는 식으로 동작한다. 이 과정에서 사용되는 기준을 pivot 이라고 한다.
2. Pivot(피벗)
농구쟁이들만 아는 피벗
퀵정렬에 사용되는 기준으로 퀵 정렬을 수행하는 과정에서 계속 어떤 값을 pivot으로 사용할 것인지 계속 명시를 해 주어야 한다.
책에서는 가장 대표적인 분할 방식인 호어 분할방식 을 기준으로 설명한다
리스트의 첫 번째 데이터를 피벗으로 정한다.이와 같이 피벗을 설정한 뒤 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서는 피벗보다 작은 데이터를 찾는다. 그 다음 각각의 데이터를 교환한다. 이 과정을 반복하다보면 하나의 피벗에 대해 정렬이 수행된다.
왼쪽과 오른쪽의 값이 엇갈릴 경우에 대해서는 오른쪽의 값을 피벗의 값과 교체함으로써 리스트를 나눈다.
3. 구현(파이썬)
퀵 정렬을 구현했을 때의 코드는 다음과 같다.
구현 과정에서 나뉜 리스트에 대한 정렬은 재귀로 반복할 수 있도록 했으며
이외의 과정은 while을 통한 조건 반복으로 처리했다.
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(array, start, end):
if start >= end:
return
pivot = start
left = start + 1
right = end
# 엇갈리기 전까지 반복 수행
while left <= right:
# 마지막 값 보다 작고, 피벗보다 큰값을 만나기 전까지 반복 수행
while left <= end and array[pivot] > array[left]:
left += 1
# 첫 번째 값보다 크고, 피벗보다 작은 값을 만나기 전까지 반복 수행
while right > start and array[pivot] <= array[right]:
right -= 1
# 엇갈렸을 경우
if left > right:
# 작은 값을 피벗과 교체
array[pivot], array[right] = array[right], array[pivot]
else:
# 엇갈리지 않았을 경우 큰 값을 피벗과 교체
array[pivot], array[left] = array[left], array[pivot]
quick_sort(array, start, right -1)
quick_sort(array, right +1, end)
quick_sort(array, 0, len(array) - 1)
print(array)4. 시간 복잡도
이렇게 구현한 퀵 정렬의 시간 복잡도는 O()으로 선택, 삽입 정렬의 O()에 비하면 빠르다는 장점을 갖고 있다.
반복을 거칠때마다 검증 횟수가 2로 나뉘어 지기때문에 이와 같은 시간복잡도를 갖는다.
하지만 최악의 경우에는 다른 정렬과 마찬가지로 의 시간복잡도를 갖는데, 이는 정렬이 되지 않은 배열보다 어느정도 거의 정렬이 된 배열에 한해 이러한 값을 갖는다.
