정렬이란?
정렬은 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 이 책에서 다루는 정렬 알고리즘은 4가지가 있다.
1. 선택 정렬(Selection Sort) - 가장 원시적인 방법
2. 삽입 정렬(Insertion Sort) - 정렬이 거의 되어 있는 상태에서는 굉장히 강력한 정렬.
3. 퀵 정렬(Quick Sort)
4. 계수 정렬(Count Sort)
이 중에서 퀵 정렬은 정렬 알고리즘 중에 가장 많이 사용되는 알고리즘이라고 할 수 있다. 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이기도 하다. 즉, 꼭 이해해야 하고 굉장히 중요한 정렬 알고리즘 이라는 뜻이다.
선택 정렬, 삽입 정렬, 계수 정렬은 한 번 읽고도 스스로 구현이 가능할 정도로 이해가 잘 되는데 퀵 정렬 같은 경우는 잘 와닿지가 않아서 이렇게 한 번 쭉 정리하면서 이해를 해보려고 한다.
퀵 정렬의 동작 방식
퀵 정렬은 간단하게 얘기하면 기준이 되는 숫자를 정하고, 그 수를 기준으로 왼쪽은 작은 수, 오른쪽은 큰 수로 반으로 나눈다. 이 과정을 계속 반복하다 보면 정렬이 되는 것이다.
여기서 기준이 되는 숫자를 피벗(Pivot)이라고 한다. 피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러 가지 방식으로 퀵 정렬을 구분하는데, 가장 대표적인 분할 방식인 호어 분할 방식을 기준으로 퀵 정렬을 구현해보았다.
호어 분할 방식에서는 이렇게 퀵 정렬을 구현한다.
- 리스트에서 첫 번째 데이터를 피벗으로 정한다.
- 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다.
- 두 데이터를 서로 교환해 준다.
- 두 데이터가 엇갈리는 경우에는 피벗과 작은 데이터의 위치를 서로 변경한다.
- 그리고 피벗을 기준으로 왼쪽 리스트와 오른쪽 리스트는 또 다시 퀵 정렬을 수행한다. 이 과정을 계속 반복한다.
- 현재 리스트의 데이터 개수가 1개 일 때 종료한다.
그림으로 이해하기
1, 2, 3, 4번 과정을 그림으로 설명하면 이렇다.
피벗(Pivot)은 가장 첫 번째 데이터인 5 이고, 왼쪽에서부터 5보다 큰 데이터를 찾고 오른쪽에서부터 5보다 작은 데이터를 찾아서 위치를 바꿔준다. 2번 정도 바꾸고 찾다보니, 왼쪽과 오른쪽이 서로 엇갈리게 된다. 이 때, 작은 데이터와 피벗의 위치를 바꿔주면, 피벗보다 왼쪽은 피벗보다 작은 데이터 리스트가,피벗보다 오른쪽은 피벗보다 큰 리스트가 만들어진다. 이 리스트들로 다시 한번 이 과정을 반복해주면 된다.
코드로 구현해보자.
코드로 구현하기
array = [5,7,9,0,3,1,6,2,4,8]
def quick_sort(array, start, end):
if start >= end:
return # start >= end 인 경우는 리스트의 원소가 1개 이하인 경우.
pivot = start # 우리는 피벗을 첫 번째 데이터로 잡기로 했다.
left = start + 1 # 왼쪽에서 부터 살피는 데이터는 두 번째 데이터 부터니까.
right = end
while left <= right:
while left <= end and array[left] <= array[pivot]: # 피벗보다 큰 데이터를 찾을 때 까지.
left += 1
while right > start and array[right] >= array[pivot]: # 피벗보다 작은 데이터를 찾을 때 까지.
right -= 1
if left > right: # 데이터가 엇갈렸다면?
array[right], array[pivot] = array[pivot], array[right] # 작은 데이터와 피벗을 교체
else:
array[right], array[left] = array[left], array[right]
# 그렇지 않다면 작은 데이터와 큰 데이터 서로 교체
quick_sort(array,start,right-1) # 왼쪽 리스트 퀵 정렬하기
quick_sort(array,right+1,end) # 오른족 리스트 퀵 정렬 하기.
확실히 글로 쓰면서 직접 구현해보니까 훨씬 이해가 잘된다.
시간 복잡도
평균적으로는 O(NlogN) 이고, 최악의 경우에는 O(N^2)이라고 한다.
