[알고리즘] 고급 정렬 알고리즘

병합 정렬 알고리즘

• 분할정복 알고리즘
  • 분할 : 1개 남을 때 까지
  • 정복 : 재귀적으로
  • 병합 : 다시 n개가 될 때까지
• 모든 원소를 다 나눈 다음에 병합하는 방식으로 정렬을 수행
• 시간 복잡도
  • O(nlogn) // 효율적 알고리즘
• 임시리스트 사용

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

    mid = len(arr)//2    
    left_arr = merge_sort(arr[:mid])    
    right_arr = merge_sort(arr[mid:])
    merged_arr = []    
    l = r = 0

    while l < len(left_arr) and r < len(right_arr):    
        #내림차순일 경우 부호 반대
        if left_arr[l] < right_arr[r]:    
            merged_arr.append(left_arr[l])    
            l += 1
        else:        
            merged_arr.append(right_arr[r])            
            r += 1        
    merged_arr += left_arr[l:]        
    merged_arr += right_arr[r:]    
    return merged_arr

print(merge_sort([4,7,3,2,6]))

퀵 정렬 알고리즘

• 분할 정복 알고리즘
  • 값에 따른 비균등 분할
  • 별도로 합치면서 정렬하는 과정 없음
• 평균적으로 매우 빠른 수행 속도 - 효율적인 알고리즘
• ==피벗==을 정한 뒤 피벗의 위치를 확정해가며 정렬을 수행
  • 피벗을 기준으로 작거나 같은 수는 왼쪽, 큰 수는 오른쪽
• 시간 복잡도
  • Worst Case : n^2
  • Average Case : nlogn

def quick_sort(arr):
    if len(arr) <= 1:
        return arr    
    pivot = arr[len(arr)//2]    
    lesser_arr, equal_arr, greater_arr = [],[],[]    
    for num in arr:    
        if num < pivot:        
            lesser_arr.append(num)        
        elif num < pivot:        
            greater_arr.append(num)        
        else:        
            equal_arr.append(num)

    return quick_sort(lesser_arr) + equal_arr + quick_sort(greater_arr)
print(quick_sort([2,3,41,5,6]))

힙 정렬 알고리즘

• 힙이라는 특수한 자료구조를 사용하는 정렬 알고리즘
• max-heapify
• min-heapify
• heapify() : 매달린 두 서브 트리가 힙성질을 만족하는 상태에서 A[k]를 루트로 하는 서브 트리 전체가 힙성질을 만족하도록 수선하는 함수

1) 주어진 배열을 힙으로 만들기
- heap : 이진 트리로서 맨 아래 층을 제외하고 완전히 채워져 있으며 맨 아래층은 왼쪽부터 채워져 있음
2) 힙에서 가장 작은 값을 차례로 제거하면서 힙의 크기 줄여나가기
- heapify()를 이용해 힙성질 만족하도록 수선
3) 아무 원소도 남지 않으면 힙 정렬 종료 ( 정렬 : 힙에서 원소들이 제거된 순서 )

• 시간 복잡도
  • O(nlogn)

def heapify(arr, i, n):
    l = i*2
    r = i*2+1
    ci = i

    if l <= n and arr[ci] < arr[l]:    
        ci = l
    if r <= n and arr[ci] < arr[r]:
        ci = r
    if ci != i:
        arr[i], arr[ci] = arr[ci], arr[i]    
        heapify(arr,ci,n)

def heap_sort(arr):
    n = len(arr)    
    arr = [0] + arr

    while n > 0:
        for i in range(n//2, 0, -1):        
            heapify(arr,i,n)        
        arr[1], arr[n] = arr[n], arr[1]        
        n -= 1        
    return arr[1:]

print(heap_sort([7,9,8,3,1,2]))