[정렬 알고리즘][파이썬] 삽입 정렬

삽입 정렬(insertion sort)은 수열의 왼쪽부터 순서대로 정렬하는 방식입니다. 작업하다 보면 좌측에는 정렬이 끝난 숫자가 오게 되고 우측에는 아직 확인하지 않은 숫자가 남게 됩니다. 우측의 미탐색 영역에서 숫자를 하나 꺼내서 정렬이 끝난 영역의 적절한 위치에 삽입해 나가는 방식입니다. -책 알고리즘 도감

 

위의 막대기들을 삽입 정렬을 사용해 오름차순으로 정렬해보겠습니다.

 

 

 

 

1. 처음에는 왼쪽 끝의 숫자(20)를 정렬이 끝났다고 간주합니다.

 

 

 

 

 

2. 아직 정렬되지 않은 숫자 중에서 왼쪽 끝에 있는 숫자(10)을 꺼내서 왼쪽에 정렬된 숫자와 비교해서 꺼낸 숫자가 더 작으면 자리를 바꿉니다.

20 > 10 이므로 20과 자리를 바꿉니다.

 

 

이제 숫자 10과 20은 정렬이 된 것으로 간주합니다. 따라서 정렬되지 않은 숫자는 30, 50, 40 세 개입니다.

 

 

 

 

3. 같은 방식으로 정렬 되지 않은 숫자 중 가장 왼쪽 숫자인 30을 꺼내서 왼쪽의 숫자들과 비교합니다.

 

30 > 20 이므로 30은 움직이지 않습니다.

 

10, 20, 30이 정렬된 상태가 되었고 이제 남은 건 50과 40입니다.

 

 

 

 

4. 같은 방식으로 정렬되지 않은 숫자들 중 가장 왼쪽에 있는 50을 꺼내서 왼쪽의 숫자와 비교합니다. 

50 > 30 이므로 50은 움직이지 않습니다.

 

이제 40만 남았습니다!

 

 

 

5. 마지막으로 40을 꺼내서 왼쪽의 숫자들과 비교합니다.

50 > 40 이므로 교체해줍니다.

다시 왼쪽에 있는 숫자와 비교하지만, 30 < 40 이므로 여기서 멈춥니다.

정렬 끝!

---

[삽입 정렬 코드] [파이썬]

출처: 코드잇

 

[출력 결과]