[Algorithm] 정렬 알고리즘 정리

1. 버블 정렬 (Bubble Sort)

개념
인접한 두 요소 비교해서, for loop으로 끝 - i 까지 교환하는 방식 반복

 

시간 복잡도

• 최악/평균: O(n^2)
• 최선: O(n) (정렬된 경우)

특징

• 구현이 쉽지만 비효율적
• 정렬된 경우 빨라질 수 있음

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j+1], arr[j] = arr[j], arr[j+1]
data = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(data)
print("Bubble Sort 결과:", data)

 

2. 병합 정렬 (Merge Sort)

개념
리스트를 길이가 1 이하가 될때까지 재귀적으로 반씩 나누고, 정렬된 부분 리스트를 역순으로 병합합니다.

 

시간 복잡도

• 최악/평균/최선: O(nlog⁡n)O(n \log n)O(nlogn)

특징

• 안정 정렬
• 추가 메모리 필요 (O(n))

def merge_sort(arr):
    n = len(arr)
    if n <= 1:
        return arr
    else:
        merge = []
        left = merge_sort(arr[:n//2])
        right = merge_sort(arr[n//2:])
        i, j = 0, 0
        while i<len(left) and j<len(right):
            if left[i] < right[j]:
                merge.append(left[i])
                i+=1
            else:
                merge.append(right[j])
                j+=1
        merge += left[i:]
        merge += right[j:]
    return merge
                
data = [64, 34, 25, 12, 22, 11, 90]
print("Merge Sort 결과:", merge_sort(data))

 

3. 퀵 정렬 (Quick Sort)

개념
병합 정렬과 유사하나, 계속 절반씩 divide하는게 아닌, pivot을 기준으로 리스트를 나누고, 재귀적으로 정렬합니다.

 

시간 복잡도

• 최악: O(n^2) (정렬된 경우)
• 평균/최선: O(nlog⁡n)

특징

• 불안정 정렬
• 추가 메모리 없이 작동 가능

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[len(arr) // 2]
    
    lesser = [x for x in arr if x < pivot]   # Elements less than the pivot
    equal = [x for x in arr if x == pivot]  # Elements equal to the pivot
    greater = [x for x in arr if x > pivot] # Elements greater than the pivot
    
    return quick_sort(lesser) + equal + quick_sort(greater)

arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print("Quick sort 결과:", sorted_arr)

 

4. 힙 정렬 (Heap Sort)

개념

최대 힙 또는 최소 힙을 사용하여 정렬합니다.

 

시간 복잡도

• 최악/평균/최선: O(nlog⁡n)

특징

• 불안정 정렬
• 추가 메모리 사용이 적음

import heapq

def heap_sort(arr):
    heapq.heapify(arr) 
    sorted_arr = [heapq.heappop(arr) for _ in range(len(arr))]
    return sorted_arr

arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = heap_sort(arr)
print("Heap sort 결과:", sorted_arr)

Min-Heap 형태:
     1
    / |
   1   2
  / | / |
 10 6 8 3

 

heap은 완전이진트리 형태의 자료구조로, 부모 노드의 값이 항상 자식 노드의 값보다 작거나 같음.

따라서 heapify()로 배열을 heap으로 만들면 위와 같은 min-heap 구조를 가지게 되고, heapq.heappop()로 가장 작은 원소를 제외한 뒤 재정렬하는 과정을 통해 heap 정렬이 가능해짐.