제너릭 메서드 설명:
https://velog.io/@vjimmny99/%EC%A0%9C%EB%84%A4%EB%A6%AD-%EB%A9%94%EC%84%9C%EB%93%9C-Generic-method
'자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘.'
다음 그림에서 볼 수 있듯이 각 반복에서 정렬되지 않은 나머지 부분 중 첫 번째 항목은 제거되어 정확한 위치에 삽입이 된다.
배열이 길어질수록 효율이 떨어진다. 다만, 구현이 간단하다는 장점이 있다.
선택 정렬이나 거품 정렬과 같은 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배 더 빠르다.
예제 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+"]");
}
}
결과