삽입정렬(Insertion Sort)

삽입정렬(Insertion Sort)

개념

• 자료 배열의 모든 요소를 앞에서부터 차례로 이미 정렬된 배열 부분과 비교해서 자신의 위치를 찾아 삽입

 

코드

def insertion_sort(arr):
    for end in range(1, len(arr)):
        for i in range(end, 0, -1):
            if arr[i - 1] > arr[i]:
                arr[i - 1], arr[i] = arr[i], arr[i - 1]

특징

• 장점
  • 안정한 정렬
  • 데이터가 이미 정렬되어 있는 경우에 효율적
  • 버블 정렬, 선택 정렬에 비해 상대적으로 빠름 
  • in-place sorting 알고리즘
• 단점
  • 여전히 비교적 많은 레코드들의 이동을 포함

시간 복잡도

• 최선(Best)
  • 이동 없이 1번의 비교만 행해짐 => O(N)
• 최악(Worst)
  • 입력 자료가 역순인 경우
  • O(N^2)

최적화 

• 불필요한 비교 작업 제거

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

 

 

참고

https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html

[알고리즘] 삽입 정렬(insertion sort)이란 - Heee's Development Blog