Types of Sorting Algorithm

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. 교육 목적: 버블, 선택, 삽입 정렬이 개념 이해에 적합

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

구현 복잡성 비교

• 버블 정렬과 선택 정렬: 두 알고리즘 모두 매우 직관적이고 이중 반복문을 사용하여 구현된다. 그러나 버블 정렬은 인접 요소의 교환에 초점을 맞추고, 선택 정렬은 최솟값을 찾아 배치하는 데 초점을 맞춘다.
• 삽입 정렬: 삽입 정렬은 카드 게임의 정렬 방식과 유사하여 직관적이다. 이미 정렬된 부분 배열에 새 요소를 올바른 위치에 삽입하는 개념을 이해하기 쉽다.
• 병합 정렬: 병합 정렬은 분할 정복을 사용하므로 재귀 호출과 병합 과정의 이해가 필요하다. 구현이 다소 복잡하지만, 로직은 명확하다.
• 퀵 정렬: 퀵 정렬은 피벗 선택과 파티셔닝 개념을 이해해야 하며, 재귀적 접근 방식을 사용한다. 효율적인 인플레이스 구현은 복잡할 수 있다.
• 힙 정렬: 힙 정렬은 이진 힙 자료구조에 대한 이해가 필요하므로 가장 복잡하다. heapify 과정과 힙 속성 유지 방법을 이해해야 한다.

성능 특성 비교

동일한 예시 배열 [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²)

적용 상황 비교

• 작은 데이터셋 (n < 50): 삽입 정렬은 구현이 간단하고 작은 데이터에서 효율적이므로 적합하다. 예를 들어, 카드 게임의 패를 정렬하는 경우 삽입 정렬이 자연스러운 선택이다.
• 대용량 데이터 (n > 1000): 퀵 정렬은 평균적으로 매우 효율적이어서 대용량 데이터에 적합하다. 예를 들어, 데이터베이스 쿼리 결과를 정렬할 때 퀵 정렬이 좋은 선택이다.
• 안정적 정렬이 필요한 경우: 학생 기록을 이름으로 정렬한 후 성적으로 다시 정렬하는 경우, 동명이인의 순서가 유지되어야 한다. 이런 경우 안정적 정렬인 병합 정렬이 적합한다.
• 최악의 경우 성능 보장이 필요한 경우: 실시간 시스템에서는 정렬 시간이 예측 가능해야 한다. 이런 환경에서는 최악의 경우에도 O(n log n)을 보장하는 병합 정렬이나 힙 정렬이 적합하다.
• 메모리 제약이 심한 환경: 임베디드 시스템과 같이 메모리가 제한된 환경에서는 추가 메모리를 거의 사용하지 않는 힙 정렬이나 인플레이스 퀵 정렬이 적합하다.

데이터 크기에 따른 효율성

• 작은 데이터 (n < 50): 삽입 정렬 > 퀵 정렬 > 병합 정렬 > 힙 정렬 > 선택 정렬 > 버블 정렬
• 중간 데이터 (50 < n < 1000): 퀵 정렬 > 병합 정렬 > 힙 정렬 > 삽입 정렬 > 선택 정렬 > 버블 정렬
• 큰 데이터 (n > 1000): 퀵 정렬 > 병합 정렬 > 힙 정렬 » 삽입 정렬 > 선택 정렬 > 버블 정렬

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

• 이미 정렬된 데이터: 삽입 정렬 > 버블 정렬 > 병합 정렬 > 힙 정렬 > 퀵 정렬(최악) > 선택 정렬
• 역순 정렬된 데이터: 퀵 정렬(피벗 최적화 필요) > 병합 정렬 > 힙 정렬 > 삽입 정렬(최악) > 버블 정렬(최악) > 선택 정렬
• 랜덤 데이터: 퀵 정렬 > 병합 정렬 > 힙 정렬 > 삽입 정렬 > 선택 정렬 > 버블 정렬
• 부분 정렬된 데이터: 삽입 정렬 > 병합 정렬 > 퀵 정렬 > 힙 정렬 > 버블 정렬 > 선택 정렬

정렬 알고리즘 종류 및 설명

버블 정렬 (Bubble Sort)

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

특징:

• 구현 난이도: 매우 간단
• 안정성: 안정적 (같은 값의 상대적 순서 유지)
• 적응성: 이미 정렬된 데이터 감지 가능
• 교환 횟수: 많음 (최악의 경우 O(n²))

시간 복잡도:

• 최선: O(n) - 이미 정렬된 경우
• 평균: O(n²)
• 최악: O(n²)

공간 복잡도:

• O(1) - 추가 메모리 거의 사용하지 않음

적합한 상황:

• 교육 목적
• 거의 정렬된 작은 데이터셋
• 정렬 상태 확인 용도

작동 과정 예시:

• 초기 배열: [8, 5, 2, 6, 9, 3, 1, 4, 7]

• 첫 번째 패스:

  1 2 3 4 5 6 7

  [8, 5, 2, 6, 9, 3, 1, 4, 7] → 8과 5 비교 및 교환 → [5, 8, 2, 6, 9, 3, 1, 4, 7] [5, 8, 2, 6, 9, 3, 1, 4, 7] → 8과 2 비교 및 교환 → [5, 2, 8, 6, 9, 3, 1, 4, 7] [5, 2, 8, 6, 9, 3, 1, 4, 7] → 8과 6 비교 및 교환 → [5, 2, 6, 8, 9, 3, 1, 4, 7] [5, 2, 6, 8, 9, 3, 1, 4, 7] → 9와 3 비교 및 교환 → [5, 2, 6, 8, 3, 9, 1, 4, 7] [5, 2, 6, 8, 3, 9, 1, 4, 7] → 9와 1 비교 및 교환 → [5, 2, 6, 8, 3, 1, 9, 4, 7] [5, 2, 6, 8, 3, 1, 9, 4, 7] → 9와 4 비교 및 교환 → [5, 2, 6, 8, 3, 1, 4, 9, 7] [5, 2, 6, 8, 3, 1, 4, 9, 7] → 9와 7 비교 및 교환 → [5, 2, 6, 8, 3, 1, 4, 7, 9]

  첫 번째 패스 후, 가장 큰 값인 9가 올바른 위치로 “버블링"되었다. 이 과정을 모든 요소가 정렬될 때까지 반복한다.

코드 예시:

 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)

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

특징:

• 구현 난이도: 간단
• 안정성: 불안정 (같은 값의 상대적 순서 변경 가능)
• 교환 횟수: 적음 (최대 n-1번)
• 비교 횟수: 항상 n(n-1)/2번

시간 복잡도:

• 최선: O(n²)
• 평균: O(n²)
• 최악: O(n²)

공간 복잡도:

• O(1) - 추가 메모리 거의 사용하지 않음

적합한 상황:

• 교환 비용이 비싼 환경
• 작은 데이터셋
• 메모리 제약이 강한 환경

작동 과정 예시:

• 초기 배열: [8, 5, 2, 6, 9, 3, 1, 4, 7]
• 첫 번째 패스:
  1. 전체 배열에서 최솟값 1을 찾는다.
  2. 1을 첫 번째 위치(인덱스 0)의 값 8과 교환한다.
  3. 배열 상태: [1, 5, 2, 6, 9, 3, 8, 4, 7]
• 두 번째 패스:
  1. 남은 배열 [5, 2, 6, 9, 3, 8, 4, 7]에서 최솟값 2를 찾는다.
  2. 2를 두 번째 위치(인덱스 1)의 값 5와 교환한다.
  3. 배열 상태: [1, 2, 5, 6, 9, 3, 8, 4, 7]
• 세 번째 패스:
  1. 남은 배열 [5, 6, 9, 3, 8, 4, 7]에서 최솟값 3을 찾는다.
  2. 3을 세 번째 위치(인덱스 2)의 값 5와 교환한다.
  3. 배열 상태: [1, 2, 3, 6, 9, 5, 8, 4, 7]

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

코드 예시:

 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)

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

특징:

• 구현 난이도: 간단
• 안정성: 안정적
• 적응성: 부분적으로 정렬된 배열에 효율적
• 온라인 알고리즘: 데이터가 들어오는 대로 정렬 가능

시간 복잡도:

• 최선: O(n) - 이미 정렬된 경우
• 평균: O(n²)
• 최악: O(n²)

공간 복잡도:

• O(1) - 추가 메모리 거의 사용하지 않음

적합한 상황:

• 작거나 거의 정렬된 데이터셋
• 온라인 데이터 처리
• 다른 정렬의 하위 루틴으로 사용

작동 과정 예시:

• 초기 배열: [8, 5, 2, 6, 9, 3, 1, 4, 7]
• 첫 번째 요소는 그 자체로 정렬되어 있다고 가정: [8]
• 두 번째 요소 5 처리:
  1. 5와 이전 요소 8을 비교한다.
  2. 5 < 8이므로 8을 오른쪽으로 이동하고 5를 삽입한다.
  3. 배열 상태: [5, 8, 2, 6, 9, 3, 1, 4, 7]
• 세 번째 요소 2 처리:
  1. 2와 이전 요소들(8, 5)을 차례로 비교합니다.
  2. 2 < 8이므로 8을 오른쪽으로 이동합니다.
  3. 2 < 5이므로 5를 오른쪽으로 이동하고 2를 삽입합니다.
  4. 배열 상태: [2, 5, 8, 6, 9, 3, 1, 4, 7]
• 네 번째 요소 6 처리:
  1. 6과 이전 요소들(8, 5, 2)을 차례로 비교한다.
  2. 6 < 8이므로 8을 오른쪽으로 이동한다.
  3. 6 > 5이므로 6을 5 다음에 삽입한다.
  4. 배열 상태: [2, 5, 6, 8, 9, 3, 1, 4, 7]
     이 과정을 나머지 요소들에 대해 계속 진행한다.

코드 예시:

 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)

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

특징:

• 구현 난이도: 중간
• 안정성: 안정적
• 분할 정복: 문제를 작은 단위로 나누어 해결
• 예측 가능한 성능: 입력에 관계없이 일정한 성능

시간 복잡도:

• 최선: O(n log n)
• 평균: O(n log n)
• 최악: O(n log n)

공간 복잡도:

• O(n) - 임시 배열 필요

적합한 상황:

• 대용량 데이터
• 안정적 정렬이 필요한 경우
• 연결 리스트 정렬 (외부 정렬)

작동 과정 예시:

• 초기 배열: [8, 5, 2, 6, 9, 3, 1, 4, 7]

• 분할 단계:

  1 2 3 4 5 6 7 8 9

  [8, 5, 2, 6, 9, 3, 1, 4, 7] / \ [8, 5, 2, 6] [9, 3, 1, 4, 7] / \ / \ [8, 5] [2, 6] [9, 3] [1, 4, 7] / \ / \ / \ / \ [8] [5] [2] [6] [9] [3] [1] [4, 7] / \ [4] [7]

• 병합 단계:

  1 2 3 4 5 6 7

  [8] [5] [2] [6] [9] [3] [1] [4] [7] \ / \ / \ / \ / [5,8] [2,6] [3,9] [1,4,7] \ / \ / [2,5,6,8] [1,3,4,7,9] \ / [1,2,3,4,5,6,7,8,9]

코드 예시:

 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)

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

특징:

• 구현 난이도: 중간
• 안정성: 불안정
• 인플레이스: 추가 메모리를 적게 사용
• 캐시 효율성: 지역성이 좋아 실제 성능이 우수

시간 복잡도:

• 최선: O(n log n)
• 평균: O(n log n)
• 최악: O(n²) - 피벗 선택이 불량할 때

공간 복잡도:

• O(log n) - 재귀 호출 스택

적합한 상황:

• 대부분의 일반적인 상황
• 평균적으로 빠른 성능이 필요할 때
• 공간 효율성이 중요할 때

작동 과정 예시:

• 초기 배열: [8, 5, 2, 6, 9, 3, 1, 4, 7]
• 첫 번째 분할: (피벗 = 8)
  1. 8을 피벗으로 선택합니다.
  2. 8보다 작은 요소들 [5, 2, 6, 3, 1, 4, 7]을 왼쪽에, 큰 요소들 [9]를 오른쪽에 배치한다.
  3. 배열 상태: [5, 2, 6, 3, 1, 4, 7, 8, 9]
• 왼쪽 부분 배열 정렬: (피벗 = 5)
  1. 5를 피벗으로 선택한다.
  2. 5보다 작은 요소들 [2, 3, 1, 4]을 왼쪽에, 큰 요소들 [6, 7]을 오른쪽에 배치한다.
  3. 배열 상태: [2, 3, 1, 4, 5, 6, 7, 8, 9]
• 왼쪽의 왼쪽 부분 배열 정렬: (피벗 = 2)
  1. 2를 피벗으로 선택한다.
  2. 2보다 작은 요소들 [1]을 왼쪽에, 큰 요소들 [3, 4]을 오른쪽에 배치한다.
  3. 배열 상태: [1, 2, 3, 4, 5, 6, 7, 8, 9]
     이런 식으로 모든 부분 배열이 정렬될 때까지 재귀적으로 진행한다.

코드 예시:

 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)

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

특징:

• 구현 난이도: 다소 복잡
• 안정성: 불안정
• 인플레이스: 추가 메모리를 거의 사용하지 않음
• 보장된 성능: 최악의 경우에도 O(n log n) 보장

시간 복잡도:

• 최선: O(n log n)
• 평균: O(n log n)
• 최악: O(n log n)

공간 복잡도:

• O(1) - 추가 메모리 거의 사용하지 않음

적합한 상황:

• 최악의 경우에도 성능 보장이 필요할 때
• 메모리 사용량이 제한적인 환경
• 부분 정렬이 필요한 경우 (top k 요소)

작동 과정 예시:

• 초기 배열: [8, 5, 2, 6, 9, 3, 1, 4, 7]

• 1단계: 최대 힙 구성
  먼저 배열을 최대 힙으로 변환한다:

  1 2 3 4 5 6 7

  9 / \ 7 8 / \ / \ 6 4 3 2 / \ 1 5

• 2단계: 정렬 수행

  1. 루트(9)와 마지막 요소(5)를 교환: [5, 7, 8, 6, 4, 3, 2, 1, 9]
  2. 힙 크기를 1 감소시키고 새 루트(5)를 적절한 위치로 이동:

  1 2 3 4 5 6 7

  8 / \ 7 3 / \ / \ 6 4 2 1 / 5

  3. 루트(8)와 마지막 요소(5)를 교환: [5, 7, 3, 6, 4, 2, 1, 8, 9]

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

코드 예시:

 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

참고 및 출처