[Algorithm] 삽입 정렬(Insertion Sort)

1. 개요

삽입 정렬(Insertion Sort)은 기준 인덱스를 정하고, 기준 인덱스 앞의 값들과 비교하여 순서에 맞는 위치에 삽입하며 정렬하는 방법을 말한다. 예제를 통해 삽입 정렬(Insertion Sort)의 동작 방식에 대해 알아보도록 하자.

2. 예제

아래와 같이 5개의 값이 들어있는 배열을 오름차순으로 정렬해보도록 하자.

1. 배열의 [1]을 기준으로 [0]의 값과 비교하여 순서가 맞는 위치에 기준 값을 넣어준다. 여기서는 [0]의 위치에 넣을 수 있다.

   

   

2. 배열의 [2]를 기준으로 [0], [1]의 값과 비교하여 순서가 맞는 위치에 기준 값을 넣어준다. 여기서는 [0]의 위치에 넣을 수 있다.

   

   

3. 배열의 [3]을 기준으로 [0], [1], [2]의 값과 비교하여 순서가 맞는 위치에 기준 값을 넣어준다. 여기서는 [1]의 위치에 넣을 수 있다.

   

   

4. 배열의 [4]를 기준으로 [0], [1], [2], [3]의 값과 비교하여 순서가 맞는 위치에 기준 값을 넣어준다. 여기서는 [1]의 위치에 넣을 수 있다.

   

   

내림차순 정렬 시, 동일한 과정으로 비교해 나가며 기준 값과 비교했을 때 내림차순을 만족하도록 정렬을 해나가면 된다.

3. 시간 복잡도

Best	Average	Worst
O(N^2)	O(N^2)	O(N^2)

두 번째 수 기준 반복문 횟수 : 1

세 번째 수 기준 반복문 횟수 : 2

…

N-1 번째 수 기준 반복문 횟수 : n - 2

N 번째 수 기준 반복문 횟수 : n - 1

∴ 총 반복문 횟수 = n(n - 1) / 2

4. 구현 코드

4-1. C++

[소스 코드]

https://github.com/dev-aiden/problem-solving/blob/main/algorithm/insertionSort.cpp

#include <iostream>
#include <vector>

using namespace std;

void insertionSortAscending(vector<int> v) {
    int size = v.size();
    int index, key;

    for (int i = 1; i < size; ++i) {
        index = i;
        key = v[i];
        for (int j = i - 1; j >= 0; --j) {
            if (key < v[j]) {
                v[j + 1] = v[j];
                index = j;
            }
        }
        v[index] = key;
    }

    cout << "오름차순 정렬 후 : ";
    for (int i = 0; i < 5; ++i) cout << v[i] << " ";
    cout << '\n';
}

void insertionSortDescending(vector<int> v) {
    int size = v.size();
    int index, key;

    for (int i = 1; i < size; ++i) {
        index = i;
        key = v[i];
        for (int j = i - 1; j >= 0; --j) {
            if (key > v[j]) {
                v[j + 1] = v[j];
                index = j;
            }
        }
        v[index] = key;
    }

    cout << "내림차순 정렬 후 : ";
    for (int i = 0; i < 5; ++i) cout << v[i] << " ";
    cout << '\n';
}

int main(void) {
    ios_base::sync_with_stdio(false);

    vector<int> v = { 5, 4, 1, 3, 2 };

    cout << "정렬 전 : ";
    for (int i = 0; i < 5; ++i) cout << v[i] << " ";
    cout << '\n';

    insertionSortAscending(v);
    insertionSortDescending(v);

    return 0;
}

[실행 결과]

4-2. JAVA

[소스 코드]

https://github.com/dev-aiden/problem-solving/blob/main/algorithm/insertionSort.java

public class InsertionSort {

    public static void main(String[] args) {
        int[] arr = {5, 4, 1, 3, 2};

        System.out.print("정렬 전 : ");
        for(int i = 0; i < 5; ++i) System.out.print(arr[i] + " ");
        System.out.println();

        insertionSortAscending(arr);
        insertionSortDescending(arr);
    }

    public static void insertionSortAscending(int[] arr) {
        int[] arr2 = arr.clone();
        int size = arr2.length;
        int index, key;

        for(int i = 1; i < size; ++i) {
            index = i;
            key = arr2[i];
            for(int j = i - 1; j >= 0; --j) {
                if(key < arr2[j]) {
                    arr2[j + 1] = arr2[j];
                    index = j;
                }
            }
            arr2[index] = key;
        }

        System.out.print("오름차순 정렬 후 : ");
        for(int i = 0; i < 5; ++i) System.out.print(arr2[i] + " ");
        System.out.println();
    }

    public static void insertionSortDescending(int[] arr) {
        int[] arr2 = arr.clone();
        int size = arr2.length;
        int index, key;

        for(int i = 1; i < size; ++i) {
            index = i;
            key = arr2[i];
            for(int j = i - 1; j >= 0; --j) {
                if(key > arr2[j]) {
                    arr2[j + 1] = arr2[j];
                    index = j;
                }
            }
            arr2[index] = key;
        }

        System.out.print("내림차순 정렬 후 : ");
        for(int i = 0; i < 5; ++i) System.out.print(arr2[i] + " ");
        System.out.println();
    }
}

[실행 결과]