Python:: 정렬 - 삽입 정렬

삽입 정렬

특정한 데이터를 적절한 위치에 '삽입'하는 방식

배열을 두 개로 나눠서 생각할 때, 좌측 배열은 이미 정렬된 상태이기 때문에 정렬된 배열 사이에 삽입함.

 

Best case : 정렬된 데이터 

Worst case : 역순으로 정렬된 데이터

 

<참고 코드>

이것이 취업을 위한 코딩 테스트다 with 파이썬 - 6.3py

https://github.com/ndb796/python-for-coding-test/blob/master/6/3.py

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(array)):
    for j in range(i, 0, -1): # 인덱스 i부터 1까지 1씩 감소하며 반복하는 문법
        if array[j] < array[j - 1]: # 한 칸씩 왼쪽으로 이동
            array[j], array[j - 1] = array[j - 1], array[j]
        else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
            break

print(array)