Sorting Algorithms 비교

정렬(Sorting) 알고리즘은 데이터를 특정 순서(오름차순/내림차순)로 정렬하는 알고리즘이다.
정렬 알고리즘은 시간 복잡도, 공간 복잡도, 안정성, 실행 속도 등의 성능 차이로 인해 다양한 방식이 존재한다.

각 정렬 알고리즘은 고유한 특성과 작동 방식을 가지고 있습니다. 여기서는 6가지 주요 정렬 알고리즘을 공통된 예시 배열 [8, 5, 2, 6, 9, 3, 1, 4, 7]을 사용하여 비교 분석하겠습니다.

정렬 알고리즘 비교

각 정렬 알고리즘은 고유한 특성과 장단점을 가지고 있으며, 적용 상황에 따라 최적의 선택이 달라진다:

  1. 작은 데이터나 거의 정렬된 데이터: 삽입 정렬이 간단하고 효율적
  2. 안정적 정렬이 필요한 경우: 병합 정렬이 가장 안정적인 O(n log n) 알고리즘
  3. 평균적으로 빠른 성능: 대부분의 경우 퀵 정렬이 최선의 선택
  4. 최악의 경우 성능 보장: 병합 정렬이나 힙 정렬이 O(n log n) 보장
  5. 메모리 제약 환경: 힙 정렬이 O(1) 공간 복잡도로 효율적
  6. 교육 목적: 버블, 선택, 삽입 정렬이 개념 이해에 적합

실제 애플리케이션에서는 이러한 특성을 고려하여 적절한 알고리즘을 선택하거나, 하이브리드 접근 방식(예: 팀소트, 인트로소트)을 사용하는 것이 일반적이다.

특성버블 정렬선택 정렬삽입 정렬병합 정렬퀵 정렬힙 정렬
시간 복잡도 (최선)O(n)O(n²)O(n)O(n log n)O(n log n)O(n log n)
시간 복잡도 (평균)O(n²)O(n²)O(n²)O(n log n)O(n log n)O(n log n)
시간 복잡도 (최악)O(n²)O(n²)O(n²)O(n log n)O(n²)O(n log n)
공간 복잡도O(1)O(1)O(1)O(n)O(log n)O(1)
안정성안정불안정안정안정불안정불안정
적응성좋음없음매우 좋음없음부분적없음
구현 난이도매우 쉬움쉬움쉬움중간중간어려움
교환 횟수많음적음중간많음중간중간
비교 횟수많음많음중간적음적음적음
온라인 가능아니오아니오예아니오아니오아니오
캐시 친화적예아니오예아니오예아니오
병렬화 가능제한적제한적아니오매우 좋음좋음제한적
실제 사용 빈도낮음낮음중간높음매우 높음중간

구현 복잡성 비교

성능 특성 비교

동일한 예시 배열 [8, 5, 2, 6, 9, 3, 1, 4, 7]에 대한 비교:

  1. 연산 횟수:
    • 버블 정렬: 약 36번의 비교, 최대 36번의 교환
    • 선택 정렬: 36번의 비교, 최대 8번의 교환
    • 삽입 정렬: 평균 20번의 비교, 20번의 이동
    • 병합 정렬: 약 19번의 비교, 30번의 이동
    • 퀵 정렬: 평균 16번의 비교, 12번의 교환
    • 힙 정렬: 약 24번의 비교, 18번의 교환
  2. 메모리 사용:
    • 버블/선택/삽입/힙 정렬: 추가 메모리 거의 사용하지 않음
    • 병합 정렬: 전체 배열 크기만큼의 추가 메모리 필요
    • 퀵 정렬: 재귀 호출을 위한 스택 공간 필요
  3. 적응성:
    • 이미 정렬된 데이터에서:
      • 버블 정렬: O(n) (교환 없음 감지 시)
      • 삽입 정렬: O(n) (비교만 수행)
      • 선택/병합/힙 정렬: 여전히 모든 연산 수행
      • 퀵 정렬: 피벗 선택에 따라 최악의 경우 O(n²)

적용 상황 비교

데이터 크기에 따른 효율성
데이터 초기 상태에 따른 효율성

정렬 알고리즘 종류 및 설명

버블 정렬 (Bubble Sort)

버블 정렬은 인접한 두 요소를 비교하여 순서가 잘못되어 있으면 교환하는 과정을 반복한다.
가장 큰 값이 배열의 끝으로 “버블링(bubbling)“되는 방식으로 작동한다.

특징:

시간 복잡도:

공간 복잡도:

적합한 상황:

작동 과정 예시:

코드 예시:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        # 정렬 완료 감지를 위한 플래그
        swapped = False
        
        # 마지막 i개 요소는 이미 정렬됨
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        
        # 교환이 없었다면 정렬 완료
        if not swapped:
            break
    
    return arr

선택 정렬 (Selection Sort)

선택 정렬은 현재 위치에 들어갈 값을 찾아 선택하는 방식이다.
매 반복마다 남은 요소 중 최솟값을 찾아 현재 위치에 배치한다.

특징:

시간 복잡도:

공간 복잡도:

적합한 상황:

작동 과정 예시:

이 과정을 계속 반복하여 배열을 정렬한다.

코드 예시:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def selection_sort(arr):
    n = len(arr)
    
    for i in range(n):
        # 현재 위치를 최솟값의 인덱스로 초기화
        min_idx = i
        
        # i부터 끝까지 탐색하여 최솟값 찾기
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        
        # 최솟값을 현재 위치와 교환
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    
    return arr

삽입 정렬 (Insertion Sort)

삽입 정렬은 정렬된 부분 배열에 새 요소를 적절한 위치에 삽입하는 방식이다.
카드 게임에서 카드를 정렬하는 방식과 유사하다.

특징:

시간 복잡도:

공간 복잡도:

적합한 상황:

작동 과정 예시:

코드 예시:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        
        # key보다 큰 요소들을 오른쪽으로 이동
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        
        # key를 올바른 위치에 삽입
        arr[j + 1] = key
    
    return arr

병합 정렬 (Merge Sort)

병합 정렬은 분할 정복 방식으로, 배열을 반으로 나누고 각 부분을 재귀적으로 정렬한 후 병합하는 방식이다.

특징:

시간 복잡도:

공간 복잡도:

적합한 상황:

작동 과정 예시:

코드 예시:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    # 분할 단계
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    # 병합 단계
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    
    # 두 배열을 비교하여 작은 값부터 결과에 추가
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    # 남은 요소들 추가
    result.extend(left[i:])
    result.extend(right[j:])
    
    return result

퀵 정렬 (Quick Sort)

퀵 정렬도 분할 정복 방식이지만, 피벗을 기준으로 작은 값과 큰 값으로 분할하여 재귀적으로 정렬한다.

특징:

시간 복잡도:

공간 복잡도:

적합한 상황:

작동 과정 예시:

코드 예시:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[len(arr) // 2]  # 중간 요소를 피벗으로 선택
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    
    return quick_sort(left) + middle + quick_sort(right)

힙 정렬 (Heap Sort)

힙 정렬은 이진 힙 자료구조를 이용하여 최대 힙(또는 최소 힙)을 구성한 후, 루트를 제거하면서 정렬한다.

특징:

시간 복잡도:

공간 복잡도:

적합한 상황:

작동 과정 예시:

이 과정을 반복하여 배열을 정렬한다.

코드 예시:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    
    # 왼쪽 자식이 루트보다 크면 largest 갱신
    if left < n and arr[left] > arr[largest]:
        largest = left
    
    # 오른쪽 자식이 루트보다 크면 largest 갱신
    if right < n and arr[right] > arr[largest]:
        largest = right
    
    # largest가 루트가 아니면 교환 및 재귀 호출
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)
    
    # 최대 힙 구성
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    
    # 요소를 하나씩 추출
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 현재 루트를 끝으로 이동
        heapify(arr, i, 0)  # 줄어든 힙에 대해 heapify 수행
    
    return arr

참고 및 출처