Quick Sort

이전까지의 알고리즘들은 시간 복잡도가 O(n^2)을 가지기 때문에 실제로 사용하기가 어려운 알고리즘이다. 그렇기 때문에 매우 빠른 알고리즘이 필요하다. 그래서 우리는 실제로 가장 많이 사용되는 알고리즘인 Quick 정렬을 배워볼 것이다.

• 대표적인 ‘분할 정복’ 알고리즘으로 평균 속도가 O(N * logN)이다. 이는 거의 상수와 비슷한 수준으로 빠르게 정렬이 가능하다.

정렬 방법

• 퀵 정렬은 하나의 큰 문제를 두 개의 문제로 분할하는 식으로 빠르게 정렬한다. 쉽게 말하자면 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눈다.

• 피벗을 기준으로 작거나 같은 데이터는 앞으로 가도록하고, 피벗보다 큰 데이터는 뒤로 가도록하여 작은 값을 갖는 데이터와 큰 값을 갖는 데이터로 분리해가며 정렬하는 방법

• 원래의 문제를 더 작은 크기의 하위 문제로 쪼개어 해결하는 ‘분할 정복 알고리즘’에 해당

• 피벗 선택 방법

• 아무 원소나 피벗으로 삼아도 상관없으나 다음과 같은 방법이 존재

위의 움직이는 사진을 보고 천천히 생각을 해보자!

• 가운데 지점을 피벗으로 잡고 , 피벗 앞으로 피벗보다 큰 숫자, 뒤는 작은 찾아 두 숫자를 바꾼다.

• 만약 앞과 뒤를 탐색하던 포인터가 같은 지점에 만났을 경우!

  • 해당 피벗을 기준으로 왼쪽 리스트를 정렬하고, 피벗 기준 오른쪽에 다시 같은 일을 반복한다.

def partition(arr, start, end):
    pivot = arr[end]
    index = start

    for i in range(start, end):
        if arr[i] <= pivot:
            arr[i], arr[index] = arr[index], arr[i]
            index += 1

    arr[index], arr[end] = arr[end], arr[index]

    return index

def quickSort(arr, left=0, right=None):
    if right is None:
        right = len(arr) - 1

    if left >= right:
        return

    pivot_index = partition(arr, left, right)

    quickSort(arr, left, pivot_index - 1)
    quickSort(arr, pivot_index + 1, right)

    return arr

# 테스트
if __name__ == "__main__":
    unsorted_list = [4, 3, 10, 6, 8, 7, 9, 1, 2, 5]
    print("Original array:")
    print(unsorted_list)

    sorted_list = quickSort(unsorted_list)
    print("Sorted array:")
    print(sorted_list)

heap 정렬

• 자료구조 힙을 사용해서 정렬을 하는 알고리즘

• heap

  • 최대 값 ,최소 값을 쉽게 추출 할 수 있는 자료 구조이며
  • 완전 이진 트리
  • 최대 힙, 최소 힙이 있음
    • max heap
      • 모든 노드의 키 값이 자식 노드의 키 값보다 항상 큼
      • 최대 힙의 루트 노드는 모든 노드 중 가장 큰 값이 위치
    • Min heap
      • 모든 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙
      • 최소 힙의 루트 노드는 노드중 가장 작은 값이 위치

• 힙 정렬

  • 주어진 배열을 힙으로 만든 다음 , 차례로 하나씩 힙에서 pop함으로써 정렬한다.

heap 정렬 알고리즘

• 정렬할 데이터들을 먼저 힙으로 삽입해야 한다.

• 그런 다음 루트 노드를 하나씩 삭제하여 꺼내면 힙에 있는 데이터들이 순서대로 나오는데 이 순서대로 나열한 것이 힙 정렬의 결과

• 최악의 경우에도 O(N * logN)의 시간 복잡도를 갖는다.

힙의 삭제 연산

• 항상 루트 노드를 삭제
• 삭제 연산이 한번 수행되어 루트 노드가 삭제 되었다면 나머지 노드들이 다시 힙의 성질을 만족해야 하므로 힙을 재구성하는 과정이 필요

힙의 삽입 연산

• 힙에 새로운 데이터가 들어오면 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입
• 삽입 후에는 힙의 성질을 만족하도록 새로운 노드를 부모 노드들과 교환

def heapify(unsorted, index, heap_size):
  largest = index
  left = 2 * index + 1
  right = 2 * index + 2
  
  if left < heap_size and unsorted[right] > unsorted[largest]:
    largest = left
    
  if right < heap_size and unsorted[right] > unsorted[largest]:
    largest = right
    
  if largest != index:
    unsorted[largest], unsorted[index] = unsorted[index], unsorted[largest]
    heapify(unsorted, largest, heap_size)

def heap_sort(unsorted):
  n = len(unsorted)
  
  for i in range(n // 2 - 1, -1, -1):
    heapify(unsorted, i, n)
    
  for i in range(n - 1, 0, -1):
    unsorted[0], unsorted[i] = unsorted[i], unsorted[0]
    heapify(unsorted, 0, i)

  return unsorted