삽입 정렬(Insertion Sort)

삽입 정렬은 현재 위치에서 자신 앞에 있는 배열들과 값을 비교 해 들어갈 위치를 찾는 방식으로 순서는 아래와 같다.

 

1. 배열의 두 번째 값을 선택한다.

2. 선택 된 값과 자신 앞의 값을 비교한다.

3. 앞의 값이 자신보다 작으면 그 자리에 멈추고, 클 경우 그 앞의 값을 비교한다.

4. 앞의 값이 자신보다 작거나 배열 첫 번째 값까지 2, 3번 과정을 반복한다.

 

최악의 경우는 선택 정렬과 마찬가지로 배열의 크기 * (n^2)의 시간복잡도 이지만, 이미 정렬이 되어 있는 경우에는 배열의 크기만큼의 시간 복잡도를 가진다.

 

코드로 구현 시 이렇게 되며, 여기에

다음과 같은 배열을 넣을 시

다음과 같은 결과값이 나온다.

간단하면서 과정을 보기 위해 3번 인덱스만 진행 순서를 보자.

 

0. 2번 인덱스까지의 작업으로 배열은 5, 7, 9, 3, 1, 8, 6, 4, 2, 0으로 되어 있다.

1. 3번 인덱스(3)의 값이 선택된다.

2. 2번 인덱스(9)과 비교해 값이 더 작으므로 1번 인덱스(7)와 비교한다.

3. 1번 인덱스(7)보다도 더 작으므로 0번 인덱스(5)와 비교한다.

4. 0번 인덱스(5)보다 더 작으므로 3번 인덱스를 0번 인덱스로 이동한다.

5. 그러므로 배열은 3, 5, 7, 9, 1, 8, 6, 4, 2, 0이 된다.

 

코드상으로는 따로 값을 담아주지만, 간단하게 생각하면 들어갈 위치에 넣고 뒤에를 다 원래 자신이 있던 위치까지 밀어준다고 생각하면 된다.