삽입정렬(Insertion Sort)

[아이디어]

1. 데이터의 가장 앞에 위치한 원소는 정렬 된 것으로 간주합니다.
2. 아직 정렬되지 않은 데이터 중 첫번째 데이터를 시작으로 정렬된 데이터와 비교해서 정렬되지 않은데이터가 작으면 정렬되지 않은 데이터와 비교된 데이터를 교환(swaping)합니다. 만약 두 데이터가 같거나 정렬되지 않은 데이터가 정렬된 데이터보다 크다면 비교를 중지합니다.
3. 인덱스 1 ~ n-1 까지의 모든 요소들에 대해 2번 로직을 실행합니다.

[특징]

1. 평균시간복잡도는 O(n²)입니다.
2. 버블, 선택 정렬에 비해 비교적 뛰어난 성능을 보여줍니다.

[구현]

data = [3, 4, 1, 0, 2, 0]
print('not-sorted:', ' '.join(map(str, data)))

for i in range(1, len(data)):
    for j in reversed(range(0, i)):
        if data[j+1] < data[j]:
            data[j+1], data[j] = data[j], data[j+1]
        else:
            break

print('sorted:', ' '.join(map(str, data)))