Data structure & Algorithms study

삽입 정렬 (Insertion Sort)

adulty22 2024. 7. 27. 22:03

삽입 정렬(Insertion Sort)은 비교 기반 정렬 알고리즘의 하나로, 마치 카드를 한 장씩 정렬하는 것처럼 리스트를 정렬한다. 이 알고리즘은 리스트를 순회하면서 현재 요소를 그 앞의 정렬된 부분과 비교하여 적절한 위치에 삽입하는 방식으로 동작한다.

동작 원리

  1. 초기 상태: 두 번째 요소부터 시작하여 리스트를 순회한다.
  2. 삽입 위치 찾기: 현재 요소를 그 앞의 정렬된 부분과 비교하여 적절한 위치를 찾는다.
  3. 교환 및 삽입: 적절한 위치를 찾으면 현재 요소를 그 위치에 삽입하고, 나머지 요소들을 오른쪽으로 이동시킨다.
  4. 반복: 리스트의 끝까지 이 과정을 반복한다.

알고리즘 단계

  1. 두 번째 요소를 선택합니다. 첫 번째 요소는 이미 정렬된 상태로 가정한다.
  2. 현재 요소를 앞의 정렬된 부분과 비교하여 적절한 위치를 찾는다.
  3. 현재 요소를 그 위치에 삽입한다.
  4. 리스트의 끝까지 이 과정을 반복한다.

예제

정렬할 리스트: [5, 2, 9, 1, 5, 6]

  1. 두 번째 요소 선택:
    • 초기 리스트: [5, 2, 9, 1, 5, 6]
    • 현재 요소: 2
    • 비교 및 삽입: 2를 5 앞에 삽입 -> [2, 5, 9, 1, 5, 6]
  2. 세 번째 요소 선택:
    • 현재 리스트: [2, 5, 9, 1, 5, 6]
    • 현재 요소: 9
    • 비교 및 삽입: 이미 정렬되어 있음 -> [2, 5, 9, 1, 5, 6]
  3. 네 번째 요소 선택:
    • 현재 리스트: [2, 5, 9, 1, 5, 6]
    • 현재 요소: 1
    • 비교 및 삽입: 1을 올바른 위치에 삽입 -> [1, 2, 5, 9, 5, 6]
  4. 다섯 번째 요소 선택:
    • 현재 리스트: [1, 2, 5, 9, 5, 6]
    • 현재 요소: 5
    • 비교 및 삽입: 5를 올바른 위치에 삽입 -> [1, 2, 5, 5, 9, 6]
  5. 여섯 번째 요소 선택:
    • 현재 리스트: [1, 2, 5, 5, 9, 6]
    • 현재 요소: 6
    • 비교 및 삽입: 6을 올바른 위치에 삽입 -> [1, 2, 5, 5, 6, 9]

리스트가 완전히 정렬되었다.

시간 복잡도

삽입 정렬의 시간 복잡도는 최악의 경우 O(n^2)이다. 최선의 경우(리스트가 이미 정렬되어 있는 경우) O(n)이다. 평균적인 경우에도 O(n^2)이다. 삽입 정렬은 작은 데이터 세트에서 효율적이며, 거의 정렬된 데이터에 대해서도 효율적으로 동작한다.

공간 복잡도

삽입 정렬은 제자리 정렬(in-place sorting) 알고리즘으로, 추가적인 메모리를 거의 사용하지 않기 때문에 공간 복잡도는 O(1)이다.

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

arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print("Sorted array is:", arr)

삽입 정렬은 간단하고 이해하기 쉬운 정렬 알고리즘이다. 특히, 거의 정렬된 데이터나 작은 데이터 세트에서 효율적으로 동작한다. 큰 데이터 세트에는 퀵 정렬(Quick Sort)이나 병합 정렬(Merge Sort) 같은 더 효율적인 알고리즘을 사용하는 것이 좋다.

 

모든 코드는 github에 저장되어 있습니다.

https://github.com/SeongUk18/Algorithm/tree/main/Data_structure_algorithms

728x90