[알고리즘] 삽입 정렬 (Insertion sort) - 자바 Java

[ 개념 ] 

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

[ 과정 설명 (오름차순) ] 

- 두 번째 요소부터 시작하여, 그 앞의 요소들과 비교하여 삽입할 위치 지정
- 두 번째 요소보다 값이 클 경우 위치를 한 칸씩 뒤로 이동 시키고, 같거나 작을 경우에는 이동을 멈추고 해당 인덱스에 요소를 삽입
- 매 순서마다 특정 요소를 어디에 삽입할 수 있는지 위치를 찾아 삽입하여 정렬

 

[ 코드 예시 (오름차순) - 자바 Java ]

public class InsertionSort {

  public static void main(String[] args) {
    int[] nums = { 9, 5, 6, 2, 4 };
    insertionSort(nums);
  }

  public static void insertionSort(int[] arr) {
    insertionSort(arr, arr.length);
  }

  private static void insertionSort(int[] arr, int arrSize) {
    for (int i = 1; i < arrSize; i++) {
      int temp = arr[i];
      int idx = i - 1;
      while (idx >= 0 && arr[idx] > temp) {
        arr[idx + 1] = arr[idx--];
      }
      arr[idx + 1] = temp;
    }
  }
}