삽입 정렬 (Insertion Sort)

삽입 정렬(Insertion Sort)

- 데이터를 하나씩 확인하면서 각 데이터를 적절한 위치에 삽입하는 방법

 

1. 원리

• 박스: 이미 정렬된 영역
• 박스 오른쪽: 아직 정렬되지 않은 영역
• n번째 원소를 1부터 n-1까지 비교해 ㅐ적절한 위치에 끼워놓고, 그 뒤에 자료를 한 칸씩 뒤로 밀어냄

 

2. 코드

array = [3, 5, 2, 8, 1]

for i in range(1, len(array)):
    for j in range(i, 0, -1): 
        if array[j] < array[j-1]:
            array[j], array[j-1] = array[j-1], array[j]
        else:
            break
            
print(array)
#[1, 2, 3, 5, 8]

 

3. 시간복잡도

O(N²)