[제로베이스] CH3. 알고리즘 - 병합정렬, 퀵정렬

병합정렬

병합 정렬은 분할 정복 (Devide and Conquer) 기법과 재귀 알고리즘을 이용해서 정렬 알고리즘이다. 즉, 주어진 배열을 원소가 하나 밖에 남지 않을 때까지 계속 둘로 쪼갠 후에 다시 크기 순으로 재배열 하면서 원래 크기의 배열로 합친다.

def merge_sort(arr):
    if len(arr) < 2:
        return arr

    mid = len(arr) // 2
    low_arr = merge_sort(arr[:mid])
    high_arr = merge_sort(arr[mid:])

    merged_arr = []
    l = h = 0
    while l < len(low_arr) and h < len(high_arr):
        if low_arr[l] < high_arr[h]:
            merged_arr.append(low_arr[l])
            l += 1
        else:
            merged_arr.append(high_arr[h])
            h += 1
    merged_arr += low_arr[l:]
    merged_arr += high_arr[h:]
    return merged_arr
    
    
list = [7, 43, 14, 44, 6, 26, 24, 3, 25, 47, 2, 32, 27, 38, 18, 17, 33, 29, 28, 0]

mergeList = merge_sort(list)
print(mergeList)

병합 결과를 담을 새로운 배열을 매번 생성해서 리턴하지 않고, 인덱스 접근을 이용해 입력 배열을 계속해서 업데이트하면 메모리 사용량을 대폭 줄일 수 있다.

def merge_sort(arr):
    
    ## 
    def sort(low, high):
        if high - low < 2:
            return
        mid = (low + high) // 2
        sort(low, mid)
        sort(mid, high)
        merge(low, mid, high)

    def merge(low, mid, high):
        temp = []
        l, h = low, mid

        while l < mid and h < high:
            if arr[l] < arr[h]:
                temp.append(arr[l])
                l += 1
            else:
                temp.append(arr[h])
                h += 1

        while l < mid:
            temp.append(arr[l])
            l += 1
        while h < high:
            temp.append(arr[h])
            h += 1

        for i in range(low, high):
            arr[i] = temp[i - low]

    return sort(0, len(arr))
    
list = [7, 43, 14, 44, 6, 26, 24, 3]#, 25, 47, 2, 32, 27, 38, 18, 17, 33, 29, 28, 0]

merge_sort(list)
print(list)

퀵정렬

병합 정렬과 마찬가지로 퀵 정렬도 분할 정복 (Devide and Conquer) 기법과 재귀 알고리즘을 이용한 정렬 알고리즘이다. 항상 정 가운데를 기준으로 분할을 하는 병합 정렬과 달리, 퀵 정렬은 흔히 피봇(pivot)이라고 불리는 임의의 기준값을 사용한다.

pivot 값을 선택하는데는 여러 가지 방법이 있지만 대개 arr[0] 값을 사용한다. 그리고 이 pivot 값을 기준으로 pivot보다 작은 값의 그룹과 pivot보다 큰 값의 그룹으로 나눕니다. 나눈 그룹을 또 같은 방식으로 정렬해나간다.

list = [6,4,7,2,8,5,2,6,9,1]
print("정렬 전 : ",list)

def quicksort(list,start,end):
  if (start>=end):
    return
  
  pivot = start
  right = end
  left = start + 1
  
  while (right >= start and left <= end ):
    while (list[pivot] < list[right]):
        right -= 1

    while (list[pivot] > list[left]):
        left += 1

    if ( right < left ):
      list[pivot], list[right] = list[right], list[pivot]
      break

    list[right], list[left] = list[left], list[right]
    right -= 1
    left += 1
      
  quicksort(list,start,right-1)
  quicksort(list,right+1,end)
    
quicksort(list,0,len(list)-1)
print("정렬 후 : ",list)