퀵 정렬
- 기준 데이터(pivot)를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼 후 리스트를 반으로 나눈다.
- pivot을 어떻게 설정하냐에 따라 여러 가지 방식으로 퀵 정렬을 구분한다.
- 다음에서 나올 퀵 정렬은 호어 분할 방식을 사용한다.
- 호어 분할 방식에서 pivot은 리스트에서 첫번째 데이터로 사용한다.
- 리스트의 왼쪽에서부터 pivot보다 큰 데이터를 찾고 리스트의 오른쪽에서부터 pivot보다 작은 데이터를 찾는다.
- 그 다음, 큰 데이터와 작은 데이터의 위치를 서로 교환해준다.
- 만약 큰 데이터의 인덱스와 작은 데이터의 인덱스가 엇갈릴 경우, 작은 데이터와 pivot의 위치를 바꾼다.
[과정]
다음과 같이 초기 데이터가 구성되어 있다고 가정한다.
pivot = '5'
왼쪽에서부터 pivot보다 큰 데이터를 찾는다. = '7'
오른쪽에서부터 pivot보다 작은 데이터를 찾는다. = '4'
둘의 위치를 바꾼다.
다시 왼쪽에서부터 pivot보다 큰 데이터를 찾는다. = '9'
오른쪽에서부터 pivot보다 작은 데이터를 찾는다. = '2'
둘의 위치를 바꾼다.
다시 왼쪽에서부터 pivot보다 큰 데이터를 찾는다. = '6'
오른쪽에서부터 pivot보다 작은 데이터를 찾는다. = '1'
둘이 엇갈리게 만났을 경우, 작은 데이터와 pivot의 위치를 바꾼다.
이렇게 되면 pivot을 기준으로 왼쪽에는 pivot보다 작은 데이터, 오른쪽에는 pivot보다 큰 데이터가 놓이게 된다.
이제 pivot을 기준으로 두개의 리스트로 나누어 위에서 했던 행동을 반복한다.
두개의 리스트로 나눈 후 각 리스트의 pivot을 설정하고 정렬을 시작한다.
'6'과 '9'같은 경우, 엇갈렸지만 '6'보다 작은 데이터가 없으므로 6의 위치는 정해진다.
뒤의 리스트 같은 경우, '9'보다 큰 데이터는 없고 작은 데이터인 '8'이 있고, 둘이 엇갈렸으니 작은 데이터와 pivot의 위치를 바꾼다.
그렇게 되면 총 3개의 리스트가 생기고, 각 pivot이 정해지게 된다.
맨 앞에 '0'을 가진 리스트는 리스트 내에 데이터의 갯수가 1개 이므로 리스트 정렬을 마치게 된다.
[결과]
[소스코드]
방법 1
data = [5,7,9,0,3,1,6,2,4,8]
def quick_sort(data, start, end):
if start>=end: #원소가 한개인 경우 종료
return
pivot=start
left=start+1
right=end
while left<=right:
# left부터 시작하여 pivot위치의 값보다 큰 데이터의 위치 찾기
while left<=end and data[left]<=data[pivot]:
left+=1
# right부터 시작하여 pivot위치의 값보다 작은 데이터의 위치 찾기
while right>start and data[right]>=data[pivot]:
right-=1
# left와 right가 엇갈렸으면
if left>right:
data[pivot],data[right]=data[right],data[pivot] # pivot의 값과 right의 값을 변경
else:
data[right],data[left]=data[left],data[right]
quick_sort(data, start, right-1)
quick_sort(data, right+1, end)
quick_sort(data, 0, len(data)-1)
print(data)
방법 2 (파이썬의 장점을 살린 퀵 정렬 소스코드)
data = [5,7,9,0,3,1,6,2,4,8]
def quick_sort(data):
if len(data)<=1: #원소가 한개인 경우 종료
return data
pivot=data[0]
tail=data[1:] #피벗을 제외한 리스트
left_side=[x for x in tail if x<=pivot]
right_side=[x for x in tail if x>pivot]
return quick_sort(left_side)+[pivot]+quick_sort(right_side)
print(quick_sort(data))
[시간복잡도]
퀵 정렬의 시간복잡도는 평균적으로 O(NlogN)이다.
퀵 정렬에서 최선의 경우를 생각해보자. 피벗 값의 위치가 변경되어 분할 할때마다 정확히 왼쪽 리스트와 오른쪽 리스트를 절반씩 분할해보면 어떨까?
데이터의 갯수가 N개 일때 logN번이 된다.
하지만 최악의 경우에는 시간 복잡도가 O(N^2)가 될 수도 있다.
데이터가 무작위로 입력되는 경우 퀵 정렬은 빠르게 동작할 확률이 높다. 하지만 리스트의 가장 왼쪽 데이터를 피벗으로 삼을 때, '이미 데이터가 정렬되어 있는 경우'에는 매우 느리게 동작한다.