[알고리즘] 삽입 정렬(insertion sort) 쉽게 이해하기! - 책 정리 알고리즘

 

삽입 정렬은 바닥에 쌓인  책을 책꽂이에 정리하는 것과 같은 알고리즘이라

 

생각하면 편하다.

 

다음 그림을 살펴보자.

 

 

책꽂이에 책이 한 권 꽂혀있고,

 

우리는 바닥에 쌓인 책도 올바른 자리에 꽂아두어야 한다.

 

이 때, 우리는 책을 시리즈 순서대로 꽂아놔야한다.

 

물론, 1권부터 뽑아서 다시 꽂을 수도 있겠지만,

 

책이 쌓여있으니 맨 위에 쌓인 책부터 알맞은 자리에 꽂아두기로 하자.

 

 

 

 

 

맨 위의 7권은 5권 뒤에 와야한다. (이미 꽂혀있는 5와 비교, 비교횟수 : 1)

 

 

3권은 제일 왼쪽에 꽂아야한다. 

 

어렵게 생각할 필요 없다. 이건 책꽂이니까..

 

아래 사진처럼 5권과 7권을 조금 밀고 3권을 맨 왼쪽에 꽂으면 된다.

 

 (이미 꽂혀있는 5, 7과 비교, 비교횟수 : 2)

 

 

이런 식으로!

 

이제 다음은 9권인데, 9권은 7권 뒤에 꽂아주고

 

 (이미 꽂혀있는 5, 7, 9와 비교, 비교횟수 : 3)

 

 

 

 

 

1권은 맨 앞에 꽂아준다.

 

 (이미 꽂혀있는 5, 7, 9, 3과 비교, 비교횟수 : 4)

 

 

4권도 알맞은 위치에 꽂아넣으면 책은 순서대로 정렬되었고..

 

 (이미 꽂혀있는 5, 7, 9, 3, 1과 비교, 비교횟수 : 5)

 

이게 삽입 정렬이다.

 

 

정렬 중간 과정은 [ 책꽂이에 꽂힌 순서 , 바닥에 놓인 순서] 이렇게 적으면 되는데,

 

중간 과정을 하나 가져와서 설명하자면,

 

 

다음 사진은 [3, 5, 7, 9, 1, 4] 상태인 것이다.

 

 

마지막으로, 과정을 숫자로만 살펴보겠다.

 

 

 

 

빨간 부분은 아직 정렬되지 않은 상태 (바닥에 쌓인 책)

 

파란 부분은 정렬된 상태이다. (책꽂이에 꽂힌 책) 

 

책꽂이를 떠올린다면, 쉽게 할 수 있을 것이다. 

 

 

다음엔 이를 C언어 코드로 구현해보도록 하겠다 :)