[알고리즘 개념] 정렬 알고리즘 - 삽입 정렬 (Insertion Sort)

정렬 알고리즘(Sorting Algorithm)

 정렬 알고리즘이란 n개로 이루어진 배열이 주어져있을 때, 이를 번호순 혹은 사전 순 같이 일정 순서대로 열거를 해주는 알고리즘을 의미한다. 데이터를 정렬하는 이유는 탐색 및 데이터 편집 시 시간을 절약하기 위해서이다. 예를 들어 정렬이 안되어 있는 데이터를 탐색하려면 데이터를 순차적으로 조사해야 하지만 정렬이 되어있을 경우 이진탐색과 같은 알고리즘을 사용하여 탐색시간을 효율적으로 줄일 수 있기 때문이다.

 

삽입 정렬 (Insertion Sort)

정렬 순서

1. 비교 대상이 되는 원소를 잡고 앞에 있는 원소들과 비교를 한다. 
2. 비교대상이 되는 원소가 이전 위치의 원소보다 작다면 swap
3. 마지막 인덱스 원소까지 1~2를 반복한다.

예시

1, 2회전 후 결과

3, 4회전 후 결과 (최종)

장점

• 구현이 쉽고 이해하기 쉽다.
• In-place Sorting Algorithm
  • 주어진 배열 내에서 이루어지기 때문에 공간복잡도 O(n)
• 대부분 정렬이 되어 있는 경우 시간복잡도가 O(n)에 수렴한다. (Best Time Complexity = O(n))
• 안정 정렬 (Stable Sorting)
  • 중복 값이 입력 순서와 동일하게 정렬 됨.

 

단점

•  O(n²)의 시간복잡도

 

시간 복잡도 

• Best Time Complexity
  • 데이터가 이미 정렬되어 있는 경우 
  • 총 비교 횟수는 n-1번이 되기 때문에 O(n)
• Worst Time Complexity
  • 데이터가 역순으로 정렬되어 있는 경우
  • 매 회전에서는 앞에 놓인 데이터들이 모두 한 칸씩 뒤로 움직여야 한다.
  • 외부 루프: T(n) = 1 +2 + ... + (n-2) + (n-1) = n(n-1)/2 ∈ O(n²)
  • 내부 교환: O(n)
  • Worst Time Complexity: O(n²) + O(n) ∈ O(n²)

 

Code (C/C++) 

#include <stdio.h>
#define LENGTH 5

// insertion Sort
void insertionSort(int* arr){
    for(int i = 1; i<LENGTH; i++) { // 두번째 원소부터 시작
        int cur = arr[i];
        int prev = i - 1;   // 이전 데이터

        // cur 데이터보다 앞에 있는 원소들 중 cur 데이터보다 큰 값이 있는 경우
        while(prev >= 0 && cur < arr[prev]) {
            arr[prev+1] = arr[prev];    // 우측으로 1칸씩 이동
            prev--;
        }
        arr[prev+1] = cur;     // 정렬 순서에 맞는 위치에 저장
    }
}

int main() {
    int arr[LENGTH] = {7,4,2,9,5};
    printf("Before Sorting: ");
    for(int i = 0; i<LENGTH; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    insertionSort(arr);

    printf("After Sorting: ");
    for(int i = 0; i<LENGTH; i++) {
        printf("%d ", arr[i]);
    }
}

 

Code (Java)

public class sorting {
    public static void main(String[] args) {
        int[] arr = {7,4,2,9,5};
        System.out.print("Before Sorting: ");
        printArr(arr);
        insertionSort(arr);
        System.out.print("After Sorting: ");
        printArr(arr);
    }

    // Print Array
    static void printArr(int[] arr) {
        int l = arr.length;
        for(int i = 0; i<l; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    
    // Insertion Sort
    static void insertionSort(int[] arr) {
        int l = arr.length;
        for(int i = 1; i < l; i++) {   // 두번째 원소부터 시작
            int cur = arr[i];
            int prev = i - 1;    // 이전 데이터

            // cur 데이터보다 앞에 있는 원소들 중 cur 데이터보다 큰 값이 있는 경우
            while(prev >= 0 && cur < arr[prev]){
                arr[prev+1] = arr[prev];    // 우측으로 1칸씩 이동
                prev--;
            }
            arr[prev+1] = cur;  // 정렬 순서에 맞는 위치에 저장
        }
    }
}