퀵 소트 알고리즘 최적화하기
100만개 random 난수 int array를 직접 만든 퀵정렬로 퀵 정렬 실행
python의 sort 및 sorted와의 실행시간을 비교해본다.
def quickSort(array,start,end):
if(start>=end):
return
pivot_idx = start
left_idx = pivot_idx + 1
right_idx = end
while left_idx<=right_idx:
while left_idx<=end and array[left_idx]<=array[pivot_idx]:
left_idx+=1
while right_idx>start and array[right_idx]>=array[pivot_idx]:
right_idx-=1
if(left_idx > right_idx):
array[pivot_idx],array[right_idx] = array[right_idx],array[pivot_idx]
else:
array[right_idx],array[left_idx] = array[left_idx],array[right_idx]
quickSort(array,start,right_idx -1)
quickSort(array,right_idx+1,end)
quickSort1 수행시간: 2.24
sort 수행시간: 0.14
sorted 수행시간: 0.15
def quickSort2(arr) :
n = len(arr)
less = []
greater = []
if n <= 1 :
return arr
else :
pivot = arr[0]
for x in arr[1:] :
if x <= pivot :
less.append(x)
else :
greater.append(x)
return quickSort2(less) + [pivot] + quickSort2(greater)
이번에는 메모리에 list를 할당해서 append하는 방식 도입
당연하겠지만, 공간복잡도는 증가
스왑하는 오버헤드가 발생하지 않기에, 더 나은 성능을 보이지만 여전히 내장 라이브러리에 비해 느린 속도
결과
quickSort2 수행시간: 1.56
sort 수행시간: 0.15
sorted 수행시간: 0.15
import time
import copy
import random
#pivot기준으로 swaping이 발생
def quickSort1(array,start,end):
if(start>=end):
return
pivot_idx = start
left_idx = pivot_idx + 1
right_idx = end
while left_idx<=right_idx:
while left_idx<=end and array[left_idx]<=array[pivot_idx]:
left_idx+=1
while right_idx>start and array[right_idx]>=array[pivot_idx]:
right_idx-=1
if(left_idx > right_idx):
array[pivot_idx],array[right_idx] = array[right_idx],array[pivot_idx]
else:
array[right_idx],array[left_idx] = array[left_idx],array[right_idx]
quickSort1(array,start,right_idx -1)
quickSort1(array,right_idx+1,end)
#swap과정을 없애는 대신, left와 right 캐싱을 위한 list를 추가로 사용함
#시간복잡도 감소, 공간복잡도 증가
#너무 많은 정수들의 입력시 스택공간이 터져버린다
def quickSort2(arr) :
n = len(arr)
less = []
greater = []
if n <= 1 :
return arr
else :
pivot = arr[0]
for x in arr[1:] :
if x <= pivot :
less.append(x)
else :
greater.append(x)
return quickSort2(less) + [pivot] + quickSort2(greater)
n = len(array)
minrun = find_minrun(n)
for start in range(0, n, minrun):
end = min(start + minrun - 1, n - 1)
insertion_sort(array, start, end)
size = minrun
while size < n:
for left in range(0, n, 2 * size):
mid = min(n - 1, left + size - 1)
right = min((left + 2 * size - 1), (n - 1))
merge(array, left, mid, right)
size = 2 * size
#list를 입력받고 실행시간 리스트를 반환하는 함수
def get_exe_time(list):
exes = []
tmp = list[:]
for i in range(3):
start = time.time()
#quicksort2
if i == 0:
quickSort1(tmp,0,len(tmp)-1)
#sort
elif i == 1:
tmp.sort()
#sorted
elif i == 2:
sorted(tmp)
end = time.time()
exes.append(round(end-start,2))
return exes
#자료구조
sorted_list = []
random_list = []
reversed_list = []
#names
names = ["random_ints.txt","sorted_ints.txt","reversed_ints.txt"]
#난수생성
for _ in range(1000000):
num = random.randint(1,10000000)
sorted_list.append(num)
random_list.append(num)
reversed_list.append(num)
#pre-sorting
sorted_list.sort()
reversed_list.sort(reverse=True)
#파일저장
for name in names:
f = open(name,"w")
if name == "random_ints.txt":
tmp_list = random_list
elif name == "sorted_ints.txt":
tmp_list = sorted_list
else:
tmp_list = reversed_list
for num in tmp_list:
f.write(str(num)+"\n")
f.close()
new_random_list = []
new_sorted_list = []
new_reversed_list = []
#File Read
for name in names:
f = open(name,"r")
if name == "random_ints.txt":
tmp_list = new_random_list
elif name == "sorted_ints.txt":
tmp_list = new_sorted_list
else:
tmp_list = new_reversed_list
for num in f:
tmp_list.append(num)
#랜덤,내림차순,오름차순 리스트별 quicksort2,sort,sorted 실행시간 반환
for idx,list in enumerate([new_random_list,new_reversed_list,new_sorted_list]):
#실행시간을 담은 리스트 -> [quicksortv2,sort,sorted]
exe_time_list = get_exe_time(list)
if idx == 0:
string = "랜덤 정수들의"
elif idx == 1:
string = "내림차순 정렬 정수들의"
else:
string = "오름차순 정렬 정수들의"
print(string+" 정렬 결과는 다음과 같습니다.")
print("quickSort2:"+str(exe_time_list[0]))
print("sort:"+str(exe_time_list[1]))
print("sorted:"+str(exe_time_list[2]))
랜덤 정수들의 정렬 결과는 다음과 같습니다.
quickSort1:2.62
sort:0.03
sorted:0.04
내림차순 정렬 정수들의 정렬 결과는 다음과 같습니다.
quickSort1:7.33
sort:0.01
sorted:0.02
오름차순 정렬 정수들의 정렬 결과는 다음과 같습니다.
quickSort1:10.33
sort:0.01
sorted:0.02
pivot의 선택이 일정할 경우, 정렬이 되어있는 리스트에서는 최악의 성능을 보이고 있다.
100만개의 리스트를 정렬하니, 높아진 공간 복잡도에의해 스택이 터져버렸다.
지금 제일 큰 문제는, 고정적인 pivot의 선택에 의해서 이미 정렬이 되어있을 경우 끔찍하게 나쁜 성능을 보이고 있다.
구글링을 통해서 알아본 결과 pivot선택을 random하게 할 경우 지금까지의 문제점을 해결할 수 있었다.
#랜덤 pivot 선택
def quickSort(arr, low, high):
if low < high:
pi = random_partition(arr, low, high)
quickSort(arr, low, pi - 1)
quickSort(arr, pi + 1, high)
def random_partition(arr, low, high):
random_pivot = random.randrange(low, high)
arr[low], arr[random_pivot] = arr[random_pivot], arr[low]
return partition(arr, low, high)
def partition(arr, low, high):
pivot = arr[low]
i = low + 1
for j in range(low + 1, high + 1):
if arr[j] < pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[low], arr[i - 1] = arr[i - 1], arr[low]
return i - 1
랜덤 정수들의 정렬 결과는 다음과 같습니다.
quickSort2:2.52
sort:0.03
sorted:0.04
내림차순 정렬 정수들의 정렬 결과는 다음과 같습니다.
quickSort2:2.19
sort:0.01
sorted:0.02
오름차순 정렬 정수들의 정렬 결과는 다음과 같습니다.
quickSort2:2.27
sort:0.01
sorted:0.02
확실히 정렬된 리스트에 대해서도 괜찮은 성능을 보이고 있다.