[Algorithm] 삽입 정렬(Insertion sort)

 

삽입 정렬 기본 개념

손 안의 카드를 정렬하는 방법과 유사하다. 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분의 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다.

삽입 정렬 구체적인 개념

삽입 정렬은 두 번째 자료부터 시작하여 그 앞의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다. 2|1, 3|2, 4|3 번째 자료와 비교한 후 삽입할 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다. 처음 Key 자료는 두 번째 자료부터 시작한다.

삽입 정렬 알고리즘 예제

import java.util.Arrays;

public class InsertionSort {

    public static void main(String[] args) {
        
        int[] unsortedArray = {9, 6, 7, 3, 5};
        System.out.println("Array Before sorting: " + Arrays.toString(unsortedArray));
        System.out.println("Array After sorting : " + Arrays.toString(insertionSort(unsortedArray)));
    }
    
    private static int[] insertionSort(int[] arr) {
        
        int arrLength = arr.length;
        
        for (int i=1; i<arrLength; i++) {
            int element = arr[i], j = 0;
            for (j=i; j>0 && arr[j-1]>element; j--) {
                arr[j] = arr[j-1];
            }
            arr[j] = element;
            
            System.out.println(i + "th element swapped : " + Arrays.toString(arr));
        }
        return arr;
    }
}

삽입 정렬 알고리즘 특징

장점
안정한 정렬 방법이다. 레코드의 수가 적을 경우 알고리즘 자체가 매우 간단하므로 다른 복잡한 정렬 방법보다 유리할 수 있다. 대부분의 레코드가 이미 정렬되어 있을 경우에는 매우 효과적일 수 있다.

단점
비교적 많은 레코드들의 이동을 포함한다. 레코드 수가 많고 레코드 크기가 클 경우 적합하지 않다.

 

단순하지만 비효율적인 방법
- 버블 정렬, 선택 정렬, 삽입정렬

복잡하지만 효율적인 방법
- 셸 정렬, 힙 정렬, 퀵 정렬, 병합 정렬

 

정렬 알고리즘 Post

[프로그래밍/Algorithm] - [Algorithm] 버블 정렬(Bubble sort)

[프로그래밍/Algorithm] - [Algorithm] 삽입 정렬(Insertion sort)

[프로그래밍/Algorithm] - [Algorithm] 선택 정렬(Selection sort)

[프로그래밍/Algorithm] - [Algorithm] 셸 정렬(Shell sort)