[알고리즘]삽입정렬이란(Insertion Sort)

▷ 목표

• 삽입정렬 알고리즘을 이해합니다.
• 삽입정렬을 이용하여 배열 오름차순을 구현할 수 있습니다.
• 삽입정렬 알고리즘의 특징
• 삽입정렬 알고리즘의 시간복잡도를 이해합니다.

▷ 제자리정렬

입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법이며
해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘입니다.

대표적으로 선택정렬, 버블정렬, 삽입정렬 등이 있습니다.

▷ 삽입정렬의 개념

 

자료 배열의 모든 요소를 순서대로 타켓으로 택한 후 자신의 앞(왼쪽) 값들과 비교하여

들어갈 위치를 찾은 후 값들을 한칸씩 뒤로 밀어낸 후 자신은 그 위치에 삽입함으로써 정렬을 완성하는 알고리즘입니다.

처음 타겟은 두번째 값부터 시작합니다.

 

<삽입정렬을 통한 배열 오름차순 자바 코드>

public class Main {
    public static int[] insertSort(int[] arr){
      for(int i=1; i<arr.length; i++){
        // 차례대로 타겟을 정합니다.
        int target = arr[i];
        // 그 앞의 원소들과 비교해야 하므로 먼저 타겟의 앞 원소를 보조 변수로 잡습니다.
        int aux = i-1;

        // 타켓의 값보다 앞의 원소가 더 클 경우 앞의 원소를 한칸 뒤로 밀어냅니다.
        // 이후 그 앞의 원소와 다시 비교해야하므로 보조 변수에서 1을 빼줍니다.
        while(aux >= 0 && arr[aux] > target){
          arr[aux+1] = arr[aux];
          aux--;
        }
        
        // 비교 후 타겟을 들어가야할 위치에 넣어줍니다.
        arr[aux+1] = target;
      }

      return arr;
    }

    public static void main(String[] args){
      int[] arr = {8, 2, 5, 6, 9};
      insertSort(arr);

      for(int x : arr) System.out.println(x);
    }
  }

▷ 삽입정렬의 특징

• 장점

    1. 안정적인 정렬 방법으로써 메모리 낭비가 적습니다.

    2. 거의 정렬 된 경우 매우 효율적이어서 최선의 경우 O(n)의 시간복잡도를 갖습니다.

• 단점

    1. 데이터의 정렬 상태에 따라서 성능의 편차가 매우 큽니다.

    2. 역순에 가까울수록 비효율적이어서 최악의 경우 O(n²)의 시간복잡도를 갖습니다.

▷ 삽입정렬의 시간복잡도

데이터의 개수가 n개라고 했을 때

• 최선의 경우 : O(n)

    비교 횟수 : (n-1)번

    앞의 값들이 모두 정렬되어 있으므로 바로 앞의 원소와 동일하게 1번의 비교만 이루어집니다.

• 최악의 경우(자료가 역순인 경우) : O(n²)

    비교 횟수

    첫번째 타겟과(두 번째에서 시작) 그 앞인 첫 번째 값을 비교하여 1번 

    두번째 타겟과 첫 번째, 두 번째 값과 비교하여 2번

    ...

    마지막 타겟과 그 앞의 값들을 비교하여 n-1번

    따라서 1 + 2 + .... + (n-2) + (n-1) → n(n-1)/2 입니다.

▷ 참고

• https://en.wikipedia.org/wiki/Insertion_sort