수를 정렬하는 방법에는 다양한 방법이 있다.
버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬.... 등등 종류가 많고 어떤 방식을 사용하냐에 따라 시간복잡도 또한 달라지게 된다.
이번 시간에는 정렬중에서도 퀵 정렬에 대해 알아보도록 하겠다.
퀵 정렬?
퀵 정렬은 기준값을 정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복하여 정렬하는 알고리즘이다.
퀵 정렬은 'quick sort'라고도 불리는데 말 그대로 빠른 정렬이다.
일반적으로 퀵 정렬은 시간 복잡도 O(nlogn)을 가지는데 퀵 정렬은 다른 정렬에 비해 특이한 점이 정말 최악의 경우에는 시간 복잡도 O(n^2)이다.
이해하기
그림으로 이해해보자.
위와 같은 num 리스트가 존재한다고 해보자.
우리는 이 리스트를 오름차순으로 정렬하고 싶다. 물론 퀵 정렬을 이용해서 말이다.
퀵 정렬을 이용할 때 맨 왼쪽의 값의 인덱스를 pivot이라고 둔다.
pivot은 이제 리스트를 양 옆에서 탐색을 할 때 '기준이 되는 값' 정도로 생각하면 된다.
그 후 pivot의 바로 오른쪽에 있는 인덱스를 left(탐색 중 가장 왼쪽)를 지정하고, 탐색 할 리스트의 범위중 가장 오른쪽에 있는 right를 지정하게 된다. left는 pivot(기준)보다 큰 경우를 처음 맞닥뜨릴 때까지 인덱스가 증가하고
right는 pivot(기준)보다 작은 경우를 처음 맞닥뜨릴 때까지 인덱스가 감소하게 된다.
그럼 위 상황에서 내가 말한대로 수행하면 어떻게 될까?
이런 상황이 되게 될 것이다.
처음 left에서 시작해 오른쪽으로 가다가 pivot보다 큰 지점인 9에서 멈추고,
가장 끝 right에서 시작해 왼쪽으로 가다가 pivot보다 작은 지점인 5에서 멈추게 된다.
그 이후 left가 가르키는 값과 right가 가르키는 값을 swap해준다.
이때 주의할 점이 2개가 있는데
- left <= right 라는 가정하에 바꾼다.
- left와 right를 바꾸는 것이 아닌 num[left],num[right]와 같이 가르키는 값을 바꾼다.
즉 이런 상황이 되는 것이다.
그 후 다시 left를 오른쪽으로 이동시키고 right를 왼쪽으로 이동시킨다(조건은 동일)
그러면 right는 6, left는 9를 가르키게 된다.(물론 실제 left와 right는 인덱스이다.)
하지만 이 경우엔 아까와 같은 방법으로 swap을 하는 것이 아니다.
왜냐하면 left <= right라는 조건을 지키지 못했기 때문이다.
이런 상황에서는 pivot의 값과 right가 가르키는 값을 교체하게 된다. 왜냐하면 right가 가르키는 값은 애초에 pivot이 가르키는 값보다 작기 때문이다.
"작기 때문에 교체한다는게 무슨 소린가?"라고 생각할 수 있다.
일단 이 조건대로 진행하자. 그 이후 설명하겠다.
교체를 하게되면 이렇게 된다.
그림 아래에도 부가설명이 들어가지만 텍스트로 한번 설명해보자면 pivot이 가르키는 값을 기준으로 했을 때 왼쪽에는 pivot이 가르키는 값보다 작은 수들로만 이루어지게 되고,
오른쪽에는 pivot이 가르키는 값보다 큰 수들로만 이루어지게 된다.
혹은 같은 수가 존재할 수도 있다.
우리가 지금까지 한 매커니즘이 이걸 위한 것이다.
"pivot을 기준으로 나누는 것"
그렇기 때문에 아까도 작기 때문에 교체한다는 것이다.
이렇게 한 과정이 끝이 난다.
이런 과정을 각 리스트로 쪼개진 범위의 길이가 1또는 0이 될 때까지 하면 된다.
마지막으로 파이썬으로 퀵 정렬 코드를 구현하고 끝마치겠다
코드 구현
def quick_sort(start,end,num):
# 리스트가 한개인 경우
if start >= end:
return
pivot = start
left,right = start + 1,end
while left <= right:
# left는 pivot보다 큰 수 찾기
while left <= end and num[left] <= num[pivot]:
left += 1
# right는 pivot보다 작은 수 찾기
while right > start and num[right] >= num[pivot]:
right -= 1
# 아직 엇갈리지 않았다면
if left <= right:
num[left],num[right] = num[right],num[left] # swap
# 엇갈렸다면
else:
num[pivot],num[right] = num[right],num[pivot] # swap
quick_sort(start,right - 1,num)
quick_sort(right + 1,end,num)
num = [7,1,4,3,9,2,6,5,8]
n = len(num)
start = 0
end = n - 1
quick_sort(start,end,num)
print(num)퀵 정렬 소감
다른 정렬에 비해 구현 자체가 굉장히 어려웠고 이론 자체를 이해하는 것도 어려웠다.
이 정렬을 공부해보니 다른 정렬은 상대적으로 쉬워보이는 느낌..
