삽입 정렬

삽입정렬은 정렬 범위를 1칸씩 확장해나가면서 새롭게 정렬 범위에 들어온 값을 기존 값들과 비교하여 알맞은 자리에 꼽아주는 알고리즘입니다.

 

예제와 함께 보는 정렬 방식 

맨 처음 두개의 값을 정렬범위로 시작합니다.

1. 1을 앞에 있는 2와 비교. (맨 첫번째 값이니 끝)

=> [2, 1, 5, 4, 3] 

더 큰 값이네? 1과 swap

=> [1, 2, 5, 4, 3] 

 

2. 한 칸을 더 확장하여 그 값을 정렬된 배열과 비교. 5를 앞에있는 2와 비교. 

=> [1, 2, 5, 4, 3]

바꿀 필요 없으니 교환하지 않고 끝.

 

3. 한 칸을 더 확장하여 4를 앞에있는 5와 비교.

=> [1, 2, 5, 4, 3] 

더 큰 값이네? 5와 swap

=> [1, 2, 4, 5, 3] 

2와 바꿀 수 없으니 비교 종료.

 

4. 한 칸을 더 확장하여 3을 앞에있는 5와 비교.

=> [1, 2, 4, 5, 3] 

더 큰 값이네? 5와 swap

=> [1, 2, 4, 3, 5] 

4와 비교. 더 큰 값이네? 4와 swap

=> [1, 2, 3, 4, 5]

2와 바꿀 수 없으니 비교 종료.

 

5. 마지막 index까지 확장하면 정렬 종료.

 

 

결국, 단계를 정리하면 아래와 같습니다.

1. 맨 처음 두개의 값을 정렬범위로 하여 비교 & swap합니다.
2. 한 칸 확장하면서 포함된 값을 이전 단계에서 정렬된 배열과 뒤에서부터 비교합니다. 
  - 비교 시, swap될 필요가 없다면 더이상 비교하지 않고 멈춥니다.
  - 비교 시, swap될 필요가 있다면 swap 후, 다시 그 앞에 있는 값과 비교합니다.
3. 다시 2번을 반복합니다.

 

 

특징은 아래로 정리할 수 있겠습니다.

1. 두번째 위치에서부터 앞의 값들과 비교한다.

2. 비교할 때는 인덱스를 하나씩 줄이면서 비교한다.

 

 

psudo 코드

for stand in range(처음부터 데이터 길이-1 번째까지):

   for j in range(stand보다 한칸 뒤 인덱스에서 1번째 인덱스까지 기준을 이동하면서):

      if 기준인덱스 j보다 그 앞 인덱스j-1 이 더 크면:

          swap(data[j], data[j-1])

     else:  # 더 크지 않으면 그 앞은 다 작은 값들일 것이므로

          break

 

* 데이터 길이-1 번째까지 로 하는 이유 : 내부 for문에서 stand+1까지 가야하기 때문에 -1을 붙여줬음.

ex) 길이가 4라면 외부 for문이 0,1,2,3까지 가 아닌 0,1,2까지 가야 내부 for문이 1,2,3까지 갈 수 있음. 

그러므로 길이 -1로, range(len(data)-1)을 해줘야함.

 

파이썬 코드

import random

data_list = random.sample(range(100), 50)
print (insertion_sort(data_list))

def insertion_sort(data):
    for stand in range(len(data)-1):
        for idx in range(stand+1, 0, -1): # 1번까지 기준은 이동.(1일 때는 0번째와 비교)
            if data[idx] < data[idx-1]:
                data[idx], data[idx-1] = data[idx-1], data[idx]
            else:
                break
    return data

# 결과값
# [0, 1, 5, 7, 9, 10, 12, 13, 14, 15, 16, 17, 19, 21, 22, 26, 27, 28, 29, 32, 33, 34, 37, 39, 
# 40, 43, 44, 49, 51, 52, 55, 61, 62, 63, 64, 66, 68, 69, 70, 71, 72, 77, 78, 83, 86, 89, 91, 95,
# 97, 98]

 

자바 코드

import java.util.Arrays;

public class 삽입정렬 {
    public static void main(String[] args) {
        int[] nonSortedArray = {4,2,1,5,3};
        // index 0은 정렬된 배열로 보고 시작합니다.
        insertionSort(nonSortedArray);
    }

    private static void insertionSort(int[] arr) {
        // 선택된 값과 그 앞에 정렬된 배열 원소 뒤에서부터 비교하면서 자리를 swap합니다.
        for (int end=1; end< arr.length; end++) {
            int i= end;
            while (i>0 && arr[i-1] > arr[i]) {  // 최적화 (더이상 작은 값을 만나면 정렬을 중단)
                swap(arr, i-1, i);
                i--;
            }
        }
        System.out.println(Arrays.toString(arr));
    }

    private static void swap(int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}

 

시간 복잡도

반복문이 2개인데, N만큼 반복하기 때문에, O(N^2)입니다.

 

또한 위 Java 코드는 기존 코드에서 최적화한 코드입니다.

만약 정렬된 배열들과 비교할 때, swap하지 않아도 되는 경우가 오면, 그 앞은 모두 정렬된 배열이므로 비교를 종료하도록 조건문을 추가했습니다.

 

이런 코드로 짰다면 총 데이터 갯수n인 정렬된 배열이 들어온다면 n-1번만 비교하면 되므로 O(N)의 시간복잡도를 가질 수 있습니다.

 

 

참고) 알고리즘이 너무 복잡해질 때는 직접 눈으로 볼 수 있는 사이트를 참고해도 좋을 것 같다.

http://pythontutor.com/visualize.html#mode=edit

Python Tutor - Visualize Python, Java, JavaScript, C, C++, Ruby code execution