QuickSort Optimization

임정환·2023년 7월 14일
논문알고리즘
0

퀵 소트 알고리즘 최적화하기

100만개 random 난수 int array를 직접 만든 퀵정렬로 퀵 정렬 실행
python의 sort 및 sorted와의 실행시간을 비교해본다.

quickSort1

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)
  • 0번째 index를 pivot으로 left,right를 만들어 swap을 반복
  • 공간복잡도는 낮지만, 높은 실행시간 ( Swap과정의 오버헤드) 
    	quickSort1 수행시간: 2.24
	sort 수행시간: 0.14
	sorted 수행시간: 0.15

quickSort2

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

중간고찰

  • Python의 sort는 기본적으로 timsort를 기반으로 하고 있다.
  • Sort 및 Sorted는 C로 작성되어있지만 , 내가 작성한 quicksort는 런타임에 한줄씩해석되어 실행되므로 훨씬 느릴 수밖에 없다.

가정

  • 100만개의 랜덤 , 내림차순, 오름차순 으로 정렬된 list를 생성하고. 각 list를 quicksort, sort, sorted로 정렬하고 실행시간을 측정해본다. 
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

quicksort

  • 시간복잡도: O(n*log(n))
  • 공간복잡도: O(logn)~O(n^2)

pivot의 선택이 일정할 경우, 정렬이 되어있는 리스트에서는 최악의 성능을 보이고 있다.

quicksort2

100만개의 리스트를 정렬하니, 높아진 공간 복잡도에의해 스택이 터져버렸다.

sort 및 sorted

  • 시간복잡도: O(n*log(n))
  • 공간복잡도: O(n)

성능차이점

  • Timsort
    삽입정렬과 병합정렬을 적절하게 이용하는 고성능의 정렬 알고리즘. 실세계의 데이터는 부분적으로 정렬된 경우가 많기 때문에 "이를 잘 활용해서 더욱 성능을 높일 수 없을까?"라는 과정에서 탄생한 정렬 알고리즘이다.
    • 런 탐지: TimSort는 먼저 데이터에서 이미 정렬된 부분 시퀀스, 즉 '런'을 찾습니다. 그런 다음 각 런이 최소한 일정 크기를 가지도록 만들기 위해 필요한 경우 삽입 정렬을 사용합니다.
    • 런 병합: 이러한 런들은 병합 정렬 알고리즘을 사용하여 병합됩니다. 이때 런들의 크기에 따라 특별한 규칙을 사용하여 런들이 병합되도록 합니다. 이러한 규칙은 런의 크기를 관리하고 불필요한 병합을 방지하여 성능을 최적화하는 데 도움이 됩니다.
  • quickSort
    start지점의 원소를 피벗으로 지정하여, 나머지 부분의 원소들에 대해서 while문을 통한 swap을 발생시킵니다. 이미 정렬이 되어있을 경우, while문이 많이 발생하게 되고 성능이 비효율적이게 됩니다.

개선된 quickSort

지금 제일 큰 문제는, 고정적인 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

확실히 정렬된 리스트에 대해서도 괜찮은 성능을 보이고 있다.

성능차이점

  • random quickSort
    pivot이 처음과는 달리 랜덤하게 생성되기 때문에 while문의 반복을 줄일 수 있었습니다.
profile
임정환
CS 박제
이전 포스트

64비트 마이그레이션 취약점

다음 포스트

TCP-KeepAlive

0개의 댓글