퀵 정렬은 divide-and-conquer 방법을 사용한 정렬로, 현재 배열에서 기준 값을 정하고 그 값 보다 작은 배열/큰 배열로 분리하면서 진행한다.
0번 인덱스의 원소를 pivot으로 설정하고, pivot 값보다 작거나 같은 값을 앞으로 큰 값을 뒤로 옮긴 후 분할한다. 한 cycle이 돌고나면 pivot이 되는 값은 최종적으로 위치가 결정되는 방법이다.
pivot 보다 작은 값/큰 값에 해당하는 리스트를 각각 만들어서 구현.
pivot이 생길 때마다 리스트가 생성되어서 메모리 낭비가 발생한다.
따라서, 구현-2의 in-place 방법으로도 구현해보았다.
import time
def quicksort(test):
if len(test) == 1: return test
pivot_idx = len(test)//2
pivot = test[pivot_idx]
pivot_min = []
pivot_max = []
for i in test[0:pivot_idx]+test[pivot_idx+1:]:
if i >= pivot : pivot_max.append(i)
elif i < pivot : pivot_min.append(i)
return quicksort(pivot_min) + [pivot] + quicksort(pivot_max)
if __name__ == '__main__':
start = time.time() # 시작 시간 저장
test = [4,6,2,8,9,7,1]
print(quicksort(test))
print("time1 :", time.time() - start) # 현재시각 - 시작시간 = 실행 시간
[1, 2, 4, 6, 7, 8, 9]
time1 : 3.1948089599609375e-05
import time
def quicksort(test, start, end):
if start >= end: return
pivot = test[start]
left = start + 1
right = end
while left <= right:
while test[left] <= pivot:
left += 1
while test[right] > pivot:
right -= 1
if left <= right:
test[left],test[right] = test[right], test[left]
else: break
test[right], test[start] = test[start],test[right]
quicksort(test, start, right-1)
quicksort(test, right+1, end)
if __name__ == '__main__':
start = time.time() # 시작 시간 저장
test = [4,6,4,2,8,9,7,1]
quicksort(test, 0, len(test)-1)
print(test)
print("time1 :", time.time() - start) # 현재시각 - 시작시간 = 실행 시간
[1, 2, 4, 4, 6, 7, 8, 9]
time1 : 3.5762786865234375e-05
불균형하게 분할되기 때문에 최악의 경우 1, n-1로 계속해서 분할하면 O(n^2)의 시간복잡도가 나온다.
하지만, 균형에 가깝게 분할되면 O(nlogn)의 시간복잡도를 가진다.
구현 - 2를 기준으로 in-place sorting 이 발생하였기 때문에 O(n)이다.