삽입 정렬 (Insertion Sort)

삽입 정렬

: 앞에서부터 차례차례 비교해나가면서 자신의 위치를 찾아 삽입하는 것을 의미한다.

 

출처: https://visualgo.net/en

 

i for문에서는 0번째 인덱스부터 차례차례 뒤로 가야하기 때문에 인덱스값이 증가하고, 반대로 j for문에서는 현재 선택한 데이터를 배열 속에서 역방향으로 비교해나간다. 만약, 이전 값이 현재 선택한 데이터보다 큰 경우 두 값의 위치를 바꿔주는 과정을 반복한다. 

 

 

파이썬으로 구현한 삽입정렬

from random import randint

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

arr = [randint(1, 50) for i in range(8)]
n = len(arr)
print(insertion_sort(arr))