[Java][알고리즘][정렬] Insertion Sort / 삽입 정렬

삽입 정렬

정렬 안된 부분의 가장 왼쪽 원소를 정렬된 부분의 적절한 위치에 '삽입' 하는 것이다.

어느 정도 정렬이 되있는 상태의 배열에서는 좋은 성능을 낼 수 있다. 하지만 만약 역으로 정렬된 경우라면 선택, 버블 정렬과 같은 성능이 나온다.

 

코드

public class Insertion {
    
    public static boolean isless(Comparable a, Comparable b) {
        return a.compareTo(b) < 0;
    }
    
    public static void swap(Comparable[] arr, int i,int j) {
        Comparable p = arr[i];
        arr[i] = arr[j];
        arr[j] = p;
    }
    
    public static void show(Comparable[] arr) {
        for(int i=0; i<arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    
    public static void Sort(Comparable[] arr) {
        for(int i=1; i<arr.length; i++) {
            for(int j=i; j>0; j--) {
                if(isless(arr[j],arr[j-1])) {
                    swap(arr,j,j-1);
                } else {
                    break;
                }
            }
            show(arr);
        }
    }
}