제너릭 메서드 설명:
https://velog.io/@vjimmny99/%EC%A0%9C%EB%84%A4%EB%A6%AD-%EB%A9%94%EC%84%9C%EB%93%9C-Generic-method

InsertionSort이란?

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

다음 그림에서 볼 수 있듯이 각 반복에서 정렬되지 않은 나머지 부분 중 첫 번째 항목은 제거되어 정확한 위치에 삽입이 된다.

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

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

코드

일반적인 Java 코드

void insertionSort(int[] arr)
{

for(int index = 1 ; index < arr.length ; index++){

  int temp = arr[index];
  int aux = index - 1;

  while( (aux >= 0) && ( arr[aux] > temp ) ) {

     arr[aux + 1] = arr[aux];
     aux--;
  }
  arr[aux + 1] = temp;

}
}

모든 타입 가능한 Java 코드

-> sentinelSort이 고전적인 Insertion sort보다 1.5배 더 빠르다.

모든 타입 가능한 Java 코드 예제 및 결과 확인.

• 모두 sentinelSort사용.

예제 1. Integer[] array = {49, 4, 36, 9, 144, 1};

public <T extends Comparable> T[] sentinelSort(T[] array) {

    System.out.print("전:");
    for (T i : array) {
        System.out.print("["+i+"]");
    }
    
    int minElemIndex = 0;
    int n = array.length;
    if (n < 1)
        return array;
    
    // put the smallest element to the 0 position as a sentinel, which will allow us to avoid
    // redundant comparisons like `j > 0` further
    for (int i = 1; i < n; i++)
        if (less(array[i], array[minElemIndex]))
            minElemIndex = i;
    swap(array, 0, minElemIndex);
    
    System.out.println();
    
    
    System.out.print(" swap 후:");
    for (T i : array) {
        System.out.print("["+i+"]");
    }
    
    System.out.println();
    for (int i = 2; i < n; i++) {
        int j = i;
        T currentValue = array[i];
        while (less(currentValue, array[j - 1])) {
            array[j] = array[j - 1];
            j--;
            System.out.print(" 과정:");
            for (T k : array) {
                System.out.print("["+k+"]");
            }
            System.out.println();
        }

        array[j] = currentValue;
    }
    System.out.println();
    
    System.out.print("후:");
    for (T i : array) {
        System.out.print( "["+i+"]");
    }

    return array;
}

/**
 * Driver Code
 */
public static void main(String[] args) {
    int size = 100_000;
    Double[] randomArray = SortUtilsRandomGenerator.generateArray(size);
    Double[] copyRandomArray = new Double[size];
    System.arraycopy(randomArray, 0, copyRandomArray, 0, size);

    InsertionSort insertionSort = new InsertionSort();
    Integer[] array = {49, 4, 36, 9, 144, 1};
    Integer[] result = insertionSort.sentinelSort(array);
    
    System.out.println();
    
    System.out.print("최종:");
    for (int i : result) {
        System.out.print( "["+i+"]");
    } }

결과

예제 2. String[] array = {"c", "a", "e", "b", "d"};

public <T extends Comparable> T[] sentinelSort(T[] array) {

    System.out.print("전:");
    for (T i : array) {
        System.out.print("["+i+"]");
    }
    
    int minElemIndex = 0;
    int n = array.length;
    if (n < 1)
        return array;
    
    // put the smallest element to the 0 position as a sentinel, which will allow us to avoid
    // redundant comparisons like `j > 0` further
    for (int i = 1; i < n; i++)
        if (less(array[i], array[minElemIndex]))
            minElemIndex = i;
    swap(array, 0, minElemIndex);
    
    System.out.println();
    
    
    System.out.print(" swap 후:");
    for (T i : array) {
        System.out.print("["+i+"]");
    }
    
    System.out.println();
    for (int i = 2; i < n; i++) {
        int j = i;
        T currentValue = array[i];
        while (less(currentValue, array[j - 1])) {
            array[j] = array[j - 1];
            j--;
            System.out.print(" 과정:");
            for (T k : array) {
                System.out.print("["+k+"]");
            }
            System.out.println();
        }

        array[j] = currentValue;
    }
    System.out.println();
    
    System.out.print("후:");
    for (T i : array) {
        System.out.print( "["+i+"]");
    }

    return array;
}

/**
 * Driver Code
 */
public static void main(String[] args) {
    int size = 100_000;
    Double[] randomArray = SortUtilsRandomGenerator.generateArray(size);
    Double[] copyRandomArray = new Double[size];
    System.arraycopy(randomArray, 0, copyRandomArray, 0, size);

    InsertionSort insertionSort = new InsertionSort();
    String[] array = {"c", "a", "e", "b", "d"};
    String[] result = insertionSort.sentinelSort(array);
    
    System.out.println();
    
    System.out.print("최종:");
    for (String i : result) {
        System.out.print( "["+i+"]");
    }
}

결과

출처: https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/sorts/InsertionSort.java