삽입 정렬(insertion sort)

삽입 정렬(insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

k번째 반복 후의 결과 배열은, 앞쪽 k + 1 항목이 정렬된 상태이다.

각 반복에서 정렬되지 않은 나머지 부분 중 첫 번째 항목은 제거되어 정확한 위치에 삽입된다. 그러므로 다음과 같은 결과가 된다.

배열이 길어질수록 효율이 떨어진다. 다만, 구현이 간단하다는 장점이 있다.

선택 정렬이나 거품 정렬과 같은 같은 O(n^2) 알고리즘에 비교하여 빠르며, 안정 정렬이고 in-place 알고리즘이다.

 

삽입 정렬의 시각화

 

 

<구현>

import java.util.*;

public class Main {
    public static int[] solution(int n, int[] arr){
        for(int i=1;i<n;i++){
            int target = arr[i], j;
            for(j=i-1;j>=0;j--){
                if(arr[j]>target) arr[j+1] = arr[j];
                else break;
            }
            arr[j+1] = target;
        }
        return arr;
    }

    public static void main(String[] args) {
      Scanner kb = new Scanner(System.in);
      int n = kb.nextInt();
      int[] arr = new int[n];

      for(int i=0;i<n;i++){
          arr[i] = kb.nextInt();
      }
      for(int e : solution(n,arr)){
          System.out.print(e + " ");
      }
    }
}

 

 

<설명>