[Python] Sort(정렬)

정렬은 Selection Sort, Bubble Sort, Quick Sort, Insertion Sort, Shell Sort, Merge Sort ...... 등으로 겁나 많다. 하지만 난 이 중에 딱 3개(Bubble Sort, Merge Sort, Quick Sort)를 짚고 넘어갈 것이다.

버블 정렬

거두절미하고 말하면 버블 정렬은 중요하지 않다. 그냥 넘어가고는 싶지만 간단하게 설명하겠다.

def bubblesort(a : list):
    for i in range(1, len(a)):
        for j in range(0, len(a) - 1):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]

위 코드를 보면 시간복잡도가 n^2이 되는 것을 알 수 있고 굉장히 비효율적이기때문에 중요하지않은 것이다.

 

 

병합 정렬

병합 정렬은 worst case, best case 모두 시간복잡도가 nlogn으로 굉장히 안정적이고 일정한 알고리즘이다. 그렇기때문에 개인적으로 병합 정렬만 알아도 상관없다고 생각한다.

(어차피 병합 정렬밖에 안쓰는데...)

 

[위키백과] Merge Sort

위 사진을 보면 병합 정렬 순서를 아주 잘 이해할 수 있을 것이다.

그리고 코드 구현을 해보자.

def mergesort(a : list):
    n = len(a)
    if n <= 1: #list를 계속 쪼개다 길이가 1이되면 return한다.
        return 
    
    mid = n // 2 #list를 계속 반으로 쪼개버릴 것이다.
    left = a[:mid] #쪼개진 list의 왼쪽은 left에 저장한다.
    right = a[mid:] #쪼개인 list의 오른쪽은 right에 저장한다.
    mergesort(left) #left를 더 반으로 쪼개서 길이가 1이 될때까지 계속 아주 조진다.
    mergesort(right) #right도 left와 같이 쪼갠다.
    
    #여기부터는 이제 left 하나, right 하나로 쪼개져서 서로 비교된 후 병합되기 시작한다.
    left_idx = 0
    right_idx = 0
    cur_idx = 0
    #left, right를 각각 left_idx, right_idx로 0부터 차례대로 서로 비교한다.
    #한 쪽이 모두 비교되어 병합될때까지 while 반복
    while left_idx < len(left) and right_idx < len(right):
        if left[left_idx] < right[right_idx]:
            #left의 left_idx 번째 값이 더 작다면 a list의 cur_idx 값은 left의 left_idx의 값이 된다.
            #쉽게말해 작은 녀석이 cur_idx번째를 차지한다.
            a[cur_idx] = left[left_idx]
            left_idx += 1 #left_idx번째 녀석은 훌륭하게 병합이 되었으니 다음 녀석으로 넘어가준다.
        else:
            #right가 더 작다면 반대로 해주면 된다.
            a[cur_idx] = right[right_idx]
            right_idx += 1
 
        cur_idx += 1 #a list의 cur_idx 자리는 더 작은 녀석이 차지했으니 다음 자리로 넘어간다.
        
    #위의 while 반복에서 left 또는 right에 계속 큰 녀석이 나와서 병합이 안된 녀석들이 있을 것이다.
    #마지막으로 이 남은 녀석들을 병합시켜주자.
    while left_idx < len(left):  #left 처리
        a[cur_idx] = left[left_idx]
        left_idx += 1
        cur_idx += 1
        
    while right_idx < len(right):  #right 처리
        a[cur_idx] = right[right_idx]
        right_idx += 1
        cur_idx += 1

주석으로 detail하게 설명했으니 도움은 될 것이다.

 

 

퀵 정렬

퀵 정렬은 피벗이라는 녀석을 기준으로 좌우를 나누는 특징이 있는데 이 때문에 파티션 교환 정렬(partition-exchange sort)라고도 불린다고 한다.

 

여기서 피벗은 기준이라고 생각하면 되겠다. 퀵 정렬은 피벗보다 작으면 왼쪽, 크면 오른쪽으로 나눠지는 방식으로 쪼개 나간다.

 

Quick Sort

 

그렇다면 피벗을 어떻게 정하는가... 일단 편의상 맨 마지막 값을 피벗으로 정해 코드 구현을 해보고 설명하겠다.

 

#스왑 : 위치가 바뀐다.
def quicksort(a, start, end): #start = 첫 번째 인덱스, end = 마지막 인덱스
    def sort(start, end):
        pivot = a[end]
        left = start
        
        for right in range(start, end):
            #start부터 end까지 계속 이동하면서 pivot보다 작으면 left 위치와 스왑된다
            if a[right] < pivot:
                a[left], a[right] = a[right], a[left]
                left += 1
                
        #for 반복문이 다 돌아 pivot보다 작은 값들이 왼쪽으로 자리를 잡았다면
        #pivot을 left(pivot보다 작은 값)와 right(pivot보다 큰 값) 중간에 위치시켜준다
        #(pivot과 left 위치를 스왑한다)
        a[left], a[end] = a[end], a[left]
        
        #pivot을 기준으로 모두 정렬을 진행했다면 left 값을 return 해준다.
        #왜냐하면 left를 기준으로 pivot보다 작은 값과 큰 값이 나누어지기 때문이다
        #그리고 pivot과 left가 서로 스왑되었기 때문에 left = pivot이 되는 것이다
        return left
    
    #start == end가 되면 곧 정렬해야할 대상이 하나 밖에 없는 것이므로 정렬할 필요가 없다
    #start < end 또는 start != end 라고 해도 상관없다 (start가 end보다 클리가 없지...)
    if start < end:
        pivot = sort(start, end)
        quicksort(a, start, pivot - 1) #pivot의 왼쪽 값들을 재귀호출
        quicksort(a, pivot + 1, end) #pivot의 오른쪽 값들을 재귀호출

퀵 정렬 또한 위 그림과 같이 비교해서보면 이해하는데 도움이 될 것이다.

 

자, 이제 퀵 정렬에 대해서 어느 정도 이해가 갔다면 피벗에 대해서 알아보자.

퀵 정렬은 피벗을 어떻게 선택하느냐에따라 Best Case 시간복잡도가 nlogn이 될 수 있고 Worst Case 시간복잡도 n^2이 될 수 있다.

예를 들어 피벗을 리스트에서 가장 작은 값 또는 가장 큰 값이 선택되었다면 피벗을 기준으로 한 쪽으로 모이는 모양새가 되어 정렬을 하나마나한 상황이 된다.

그렇다면 도대체 피벗을 정하는가

피벗을 선택하는 알고리즘을 개선해 퀵 정렬을 좀 더 최적화하는 다양한 연구 결과가 이미 많이 나와있다. 그 중에 피벗을 선택하는 아주 간단한 알고리즘을 보자.

#a = list
n = len(a)
#list a의 첫 번째, 중간, 마지막 값들을 인덱스와 함께 리스트에 저장해준다
pivots = [[a[0],0], [a[n//2], n // 2], [a[n - 1], n - 1]]]
#list 값들을 기준으로 sort해준다
pivots.sort(key=lambda x: x[0])
#sort한 pivots list에서 1번 인덱스에 있는 값이 그나마 중간 값이기때문에 pivot으로 지정한다
pivot = pivots[1][1]

피벗은 이런 식으로 정한다라고 이해하고 넘어가자... 어차피 거의 병합 정렬만 쓸테니...