[알고리즘] 삽입 정렬(Insertion Sort)

삽입 정렬(Insertion Sort)

삽입 정렬은 손안의 카드를 정렬하는 방법(새로운 카드를 기존의 정렬된 카드 사이에 올바른 위치에 삽입)과 유사하다. 또한 삽입 정렬은 선택 정렬과 유사하지만, 좀 더 효율적인 정렬 알고리즘이다.

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

 

 

정렬 과정

2번째 위치(index)의 값부터 정렬을 시작한다.

1. 해당 인덱스(key 값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스로 복사
2. 이를 key 값이 더 큰 데이터를 만날 때까지 반복
3. 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동

출처 : https://gyoogle.dev/blog/algorithm/Insertion%20Sort.html

출처 : https://rninche01.tistory.com/entry/%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-01-%EC%82%BD%EC%9E%85-%EC%A0%95%EB%A0%AC

 

 

파이썬 코드

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        for j in range(i, 0, -1):
            if arr[j - 1] > arr[j]:
                arr[j - 1], arr[j] = arr[j], arr[j - 1]
            else:
                break
    return arr

혹은

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

 

 

 

 

 

 

 

 

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

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

https://rninche01.tistory.com/entry/%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-01-%EC%82%BD%EC%9E%85-%EC%A0%95%EB%A0%AC

[정렬 알고리즘] 01 삽입 정렬(Insertion Sort)이론 및 구현

https://gyoogle.dev/blog/algorithm/Insertion%20Sort.html

삽입 정렬(Insertion Sort) | 👨🏻‍💻 Tech Interview

https://www.fun-coding.org/Chapter12-insertionsorting.html

파이썬과 컴퓨터 사이언스(기본 알고리즘): 삽입 정렬 (insertion sort) - 잔재미코딩