정렬 알고리즘 완벽 비교 버블, 선택, 삽입 정렬 이해하기

정렬 알고리즘이란 무엇인가?

정렬 알고리즘은 데이터를 정리하여 더 쉽게 검색하고 사용할 수 있도록 하는 과정입니다.

다양한 정렬 알고리즘이 존재하지만, 각각의 장단점과 사용 사례가 다릅니다.

이번 포스팅에서는 정렬 알고리즘의 기초인 버블 정렬, 선택 정렬, 삽입 정렬의

동작 원리와 특징을 비교하며 정리해 보겠습니다.

 

 

정렬 알고리즘의 동작 원리와 비교

1. 버블 정렬 (Bubble Sort)

• 정의 : 인접한 두 요소를 반복적으로 비교하며 교환하여 정렬하는 알고리즘입니다.
• 특징
  • 단순한 구현
  • 비효율적인 시간 복잡도 : 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], arr[j+1] = arr[j+1], arr[j]
    return arr

arr = [64, 34, 25, 12, 22, 11, 90]
print("버블 정렬 결과:", bubble_sort(arr))

2. 선택 정렬 (Selection Sort)

• 정의 : 배열에서 가장 작은 값을 선택하여 맨 앞의 요소와 교환하는 방식입니다.
• 특징
  • 메모리 사용량이 적음
  • 시간 복잡도 : O(n²)
• 코드 예제

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = 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

arr = [64, 25, 12, 22, 11]
print("선택 정렬 결과:", selection_sort(arr))

3. 삽입 정렬 (Insertion Sort)

• 정의 : 현재 요소를 적절한 위치에 삽입하여 정렬하는 방식입니다.
• 특징
  • 거의 정렬된 배열에서는 매우 효율정
  • 시간 복잡도 : 최선 O(n), 최악 O(n²)
• 코드 예제

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

arr = [12, 11, 13, 5, 6]
print("삽입 정렬 결과:", insertion_sort(arr))

4. 정렬 알고리즘 비교

• 시간 복잡도
  • 버블 정렬 : 항상 O(n²)
  • 선택 정렬 : 항상 O(n²)
  • 삽입 정렬 : 최선 O(n), 최악 O(n²)
• 장단점
  • 버블 정렬 : 가장 단순하지만 비효율적
  • 선택 정렬 : 메모리 사용량이 적지만 느림
  • 삽입 정렬 : 거의 정렬된 배열에서 효율적

 

 

정렬 알고리즘 학습의 중요성

정렬 알고리즘은 데이터를 효율적으로 처리하기 위한 첫걸음입니다.

버블 정렬, 선택 정렬, 삽입 정렬과 같은 기초 알고리즘은 단순하지만,

더 복잡한 알고리즘을 배우기 위한 기초가 됩니다.

데이터의 특성과 상황에 따라 적합한 정렬 알고리즘을 선택하는 것이 중요합니다.

다음에는 퀵 정렬과 병합 정렬 같은 고급 정렬 알고리즘을 다뤄보겠습니다.