[알고리즘] 삽입 정렬(insertion sort)

 

# insertion sort

def insertion_sort(data):
    for idx1 in range(len(data) - 1):
    	# 처음에 range(idx1 + 1, len(data) - 1)로 적었다.
        for idx2 in range(idx1 + 1, 0, -1):
            if data[idx2] < data[idx2 - 1]:
            	# 이 부분은 swap이 아니라 data[idx2] = data[idx2 - 1]로 적었다.
                data[idx2], data[idx2 - 1] = data[idx2 - 1], data[idx2]
            else:
                break
    return data

import random
data = random.sample(range(100), 10)
print(insertion_sort(data))

len(data) - 1 회 반복하면서,

idx1 + 1부터 바로 앞 요소와 비교해서 바로 앞 요소가 더 작거나 같을 때까지 swap하면서 idx를 하나씩(-1) 줄여나간다.