quick sort | 퀵 정렬

이 글은 python3를 기준으로 작성했다.

출처 : 위키피디아 "퀵 정렬"

 

다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.

퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다.

퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고(그 이유는 메모리 참조가 지역화되어 있기 때문에 CPU 캐시의 히트율이 높아지기 때문이다.), 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다. 또한 매 단계에서 적어도 1개의 원소가 자기 자리를 찾게 되므로 이후 정렬할 개수가 줄어든다. 때문에 일반적인 경우 퀵 정렬은 다른 O(n log n) 알고리즘에 비해 훨씬 빠르게 동작한다. 이러한 이유로 퀵소트(빠른정렬)라는 이름의 기원이 되었다. 그리고 퀵 정렬은 정렬을 위해 O(log n)만큼의 memory를 필요로한다.

원소들 중에 같은 값이 있는 경우 같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있어 불안정 정렬에 속한다. 이러한 경우의 C코드 예: 51, 52, 3, 2, 1 를 정렬하면 1, 2, 3, 52, 51 이 된다.

 

출처 : 위키피디아 "퀵 정렬"

divide and conquer를 이용하는 정렬.

 

merge sort가 combine하는 과정이 어렵다면

 

quick sort는  divide하는 과정이 어렵다.

 

퀵 정렬은 다음과 같은 순서로 진행된다.

1. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
3. 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.

재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

 

 

Code

---

partition 함수

def partition(my_list, start, end):
    pivot = my_list[end]
    b = start
    for i,v in enumerate(my_list[:end]):
        if v < pivot:
            temp = my_list[i]
            my_list[i] = my_list[b]
            my_list[b] = temp
            b += 1
    
    temp = my_list[end]
    my_list[end] = my_list[b]
    my_list[b] = temp
    
    return b

pivot은 리스트의 마지막 index로 설정

 

pivot을 선정하는 방식은 자유로우나 주로 첫지점, 중간지점, 끝지점 중 하나를 선택함.

 

 

quicksort 함수

def quicksort(my_list, start=0, end=None):
    
    if end == None:
        end = len(my_list)-1
    
    #base case
    if end - start<1:
        return
    p = partition(my_list,start,end)
    quicksort(my_list,start,p-1)
    quicksort(my_list,p+1,end)

merge sort는 쪼개고 합치면서 정렬된 새로운 리스트를 복사해 return 하지만

 

quick sort는 기존의 리스트의 값을 정렬하는 것이기에 함수에 return 하는 값이 없다.

 

필력이 최악이니 코드로 보자.

 

비교에 사용된 merge sort 함수와 quick sort 함수

## merge sort ###
def merge(list1, list2):
    rst = []
    while len(list1)>0 and len(list2)>0:
        temp = list1.pop(0) if list1[0] < list2[0] else list2.pop(0)
        rst.append(temp)
    
    rst = rst + list1 if len(list1)>0 else rst + list2
    return rst

def merge_sort(my_list):
    if len(my_list)>1:
        mid = len(my_list)//2
        return merge(merge_sort(my_list[:mid]),merge_sort(my_list[mid:]))
    return my_list
##################
## quick sort ####
def partition(my_list,start,end):
    pivot = end
    i = start
    b = start
    
    while i<p:
        if my_list[i]<my_list[p]:
            
            temp = my_list[i]
            my_list[i] = my_list[b]
            my_list[b] = my_list[i]
            
            b += 1
        i += 1
    temp = my_list[p]
    my_list[p] = my_list[b]
    my_list[b] = my_list[p]
    
def quicksort(my_list, start=0, end=None):
    
    if end == None:
        end = len(my_list)-1
    
    #base case
    if end - start<1:
        return
    p = partition(my_list,start,end)
    quicksort(my_list,start,p-1)
    quicksort(my_list,p+1,end)
    
####################

 

비교

##merge sort##
mylist = [3, 8, 5, 7, 9, 7,15, 13, 11]
print("mylist의 주소값 : {}".format(id(mylist)))
mylist = merge_sort(mylist)
print("merge_sort mylist의 주소값 : {}".format(id(mylist)))

##quick sort##
mylist = [3, 8, 5, 7, 9, 7,15, 13, 11]
print("mylist의 주소값 : {}".format(id(mylist)))
quicksort(mylist,0,len(mylist)-1)
print("quicksort mylist의 주소값 : {}".format(id(mylist)))

##결과
# mylist의 주소값 : 1943523930632
# merge_sort mylist의 주소값 : 1943523732808
# mylist의 주소값 : 1943523930632
# quicksort mylist의 주소값 : 1943523930632

merge sort를 사용한 후, mylist의 주소가 바뀌었지만,

quick sort를 사용한 후에는 주소가 바뀌지 않았다.