데이터를 특정한 기준에 정렬하기 위해 사용하는 알고리즘입니다.

정렬이 사용되는 핵심 유형

• 그리디
• 이진 탐색

대표적인 정렬의 종류

대표적인 정렬 라이브러리를 성능에 따라서 비교하면 다음과 같습니다.

O(n²)의 시간 복잡도 (정렬할 자료의 수가 늘어나면 제곱에 비례해서 증가)

• 버블 정렬(Bubble Sort)
  • 버블 정렬은 바로 옆에 있는 것과 비교해서 정렬하는 것입니다. 구현은 쉽지만 효율성이 매우 낮다고 알려져 있습니다.
• 선택 정렬(Selection Sort)
  • 가장 작은 데이터를 선택해서 정렬되지 않은 데이터 중 가장 앞 쪽에 있는 데이터와 위치를 바꾸는 방법
• 삽입 정렬(Insertion Sort)
  • 데이터를 앞에서부터 하나씩 확인하며 데이터를 적절한 위치에 삽입하는 방법

O(n log n)의 시간 복잡도

• 병합 정렬(Merge Sort) ⭐️

  • 합병 정렬 또는 병합 정렬은 O(n log n) 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나 입니다.

• 퀵 정렬(Quick Sort) ⭐️

  • 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
  • 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n²)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행합니다.

• 힙 정렬 ⭐️⭐️

  		 1  ---> root (최솟값)
     /   \\
    3     5
   / \\   /
  4   8 7
  

  • 힙이란? (최소 힙 기준)

    • 부모 노드의 키가 자식 노드의 키보다 작게 구성된 완전 이진 트리
    • 중복 값을 허용하는 트리

  • 힙 정렬이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최소 힙을 구성하고 오름차순 정렬을 위해서는 최대 힙을 구성하면 됩니다.

  • 힙 정렬 시간 복잡도 : O(n log n)

  • 파이썬의 heapq 모듈을 통해 사용 가능

  • heapq 모듈은 이진 트리(binary tree) 기반의 최소 힙(min heap) 자료구조를 제공

    • heapq.heapify()
      • 이미 원소가 들어있는 리스트 → 힙 구조로 재구성.
        • heapify(heap)
      • 함수의 성능은 인자로 넘기는 리스트의 원소수에 비례합니다.
      • 즉 O(n)의 시간 복잡도를 가집니다.
    • heapq.heappop()
      • 원소를 삭제할 대상 리스트를 인자로 넘기면, 가장 작은 원소를 삭제 후에 그 값을 리턴합니다.
        • heappop(heap)
      • 내부적으로 이진 트리로 부터 원소를 삭제하는 heappop() 함수도 역시 O(log(n))의 시간 복잡도를 가집니다.
    • heapq.heappush
      • 힙에 원소를 추가할 수 있습니다
      • 첫번째 인자는 원소를 추가할 대상 리스트이며 두번째 인자는 추가할 원소를 넘깁니다.
        • heappush(heap, 4)
      • 내부적으로 이진 트리에 원소를 추가하는 heappush() 함수는 O(log(n))의 시간 복잡도를 가집니다.

  • 최대 힙

    • 힙에 튜플(tuple)를 원소로 추가하거나 삭제하면, 튜플 내에서 맨 앞에 있는 값을 기준으로 최소 힙이 구성되는 원리를 이용

      from heapq import heappush, heappop
      
      nums = [4, 1, 7, 3, 8, 5]
      heap = []
      
      for num in nums:
        heappush(heap, (-num, num))  # (우선 순위, 값)
      
      while heap:
        print(heappop(heap)[1])  # index 1
      

  • 그래서 힙 정렬은 어떻게?

    from heapq import heappush, heappop
    
    def heap_sort(nums):
      heap = []
      for num in nums:
        heappush(heap, num)
    
    	# 위 과정을 heapify로 단순화시킬 수 있다.
    
    	# 최소값을 하나씩 반환 -> 이 과정에서 n * log(n)이 걸린다
      sorted_nums = []
      while heap:
        sorted_nums.append(heappop(heap))
      return sorted_nums
    
    print(heap_sort([4, 1, 7, 3, 8, 5]))
    
    

• 구현 코드