삽입 정렬(insertion sort)

1) 삽입 정렬(insertion sort) 이란?

- 삽입 정렬은 두 번째 인덱스부터 시작

- 해당 인덱스 앞에 있는 데이터(왼쪽)부터 비교해서 인덱스 값이 더 작으면 데이터(왼쪽)을 해당 인덱스 값 뒤로 복사

- 이를 인덱스 값이 더 큰 데이터를 만날 때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 인덱스 값을 이동

File:Insertion-sort-example.gif - Wikimedia Commons

 

2) 알고리즘 구현

 

▼ 파이썬

def insertion_sort(data):
    for idx in range(len(data) - 1):
        for idx2 in range(idx + 1, 0, -1):
            if data[idx2] < data[idx2 - 1]:
                data[idx2], data[idx2 - 1] = data[idx2 - 1], data[idx]
            else:
                break
    return data

1. for idx in range(len(data) - 1) 로 반복

2. for idx2 in range(idx + 1, 0, -1) 로 반복

   - idx 가 1 이면 for idx2 in range(2, 0, -1) 

   -> 2 에서부터 0 까지 -1 씩이므로 2, 1

3. 내부 반복문 안에서 data[idx2] < data[idx2 - 1] 이면, data[idx2] 와 data[idx2 - 1] 자리 바꿈

 

결과

import random

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

 

 

▼ 자바

void insertionSort(int[] arr) {
    for(int idx = 1; idx < arr.length; idx++) {	// 1.
    	int tmp = arr[idx];
        int prev = idx - 1;
        while( (prev >= 0) && (arr[prev] > tmp) ) {	// 2.
            arr[prev + 1] = arr[prev];
            prev--;
        }
        arr[prev + 1] = tmp;				// 3.
    }
    System.out.println(Arrays.toString(arr));
}

1. 첫 번째 데이터(idx 기준으로 왼쪽)의 위치와 비교할 두 번째 데이터의 위치(idx) 를 기준으로 반복

   - tmp = arr[idx] 로 인덱스 값을 저장하고, prev = idx - 1 로 인덱스 값의 왼쪽 데이터 위치를 저장한다.

2. 인덱스의 왼쪽 데이터를 가리키는 prev 가 음수가 되지 않아야 하며, 해당 prev 의 값이 인덱스의 데이터 보다 크다면 서로의 데이터의 자리를 바꿔준다.

3. 모든 반복문이 완료된 후, prev 에는 현재 tmp 값보다 작은 값들 중 제일 큰 값의 위치(idx) 를 가리키게 된다. 따라서 prev + 1 의 위치에 tmp 값을 삽입해준다.

 

 

 

3) 알고리즘 분석

- 반복문이 두 개인 형태이므로, O(n^2)

  단, 최악의 경우에는 {n*(n-1)}/2

- 완전 정렬이 되어 있는 상태라면 최선은 O(n)

 

 

 

참고)

1. File:Insertion-sort-example.gif - Wikimedia Commons

File:Insertion-sort-example.gif - Wikimedia Commons

2. 패스트캠퍼스 '코딩 알고리즘 온라인 완주반'

3. 삽입 정렬(Insertion Sort) | 👨🏻‍💻 Tech Interview (gyoogle.dev)

삽입 정렬(Insertion Sort) | 👨🏻‍💻 Tech Interview