자바로 풀어보는 삽입정렬(InsertSort)

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

정렬 과정 (N개의 정렬을 할 숫자가 있다고 가정)

1.  한 개의 값을 포함하는 목록으로 시작한다. 

2.  두 개의 값을 비교하고, 적합한 위치에 삽입한다. 

3. 세 개의 값을 처음 두 개의 값과 비교하여 위치에 삽입한다.

두 가지의 버전으로 작성하였다. 하나는 재귀를 이용한. 하나는 단순 for문이다.

public class InsertSort {
    private static int[] array;
 
    public static void init(int length) {
        array = new int[length];
 
        for (int i = 0; i < length; i++) {
            array[i] = (int) (Math.random() * 45) + 1;
        }
    }
 
    private static void swap(int[] array, int source, int target) {
        int tmp = array[source];
        array[source] = array[target];
        array[target] = tmp;
    }
 
    public static void printArray(int[] array) {
        for (int i : array) {
            System.out.print(i + " ");
        }
 
        System.out.println();
    }
 
    public static void main(String[] args) {
        init(10);
        printArray(array);
        insertSort(array);
        printArray(array);
    }
    
    public static void insertSort(int[] array) {
        insertSort(array, 1);
    }
    
    public static void insertSort(int[] array, int start) {
        if(start < array.length) {
            int standard = array[start];
            int compareIndex = start-1;
            
            while(compareIndex >= 0 && array[compareIndex] > standard) {
                array[compareIndex + 1] = array[compareIndex];
                compareIndex--;
            }
            
            array[compareIndex + 1] = standard;
            insertSort(array, start+1);
        }
    }
}

public class InsertSortExample {
    public static void main(String[] args) {
        int[] arr = { 10, 2, 6, 4, 3, 7, 5 };
        
        for(int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
        
        for(int i=1; i < arr.length; i++) {
            int standard = arr[i];
            int compareIndex = i-1;
            
            while(compareIndex >= 0 && standard < arr[compareIndex]) {
                arr[compareIndex+1] = arr[compareIndex];
                compareIndex--;
            }
            
            arr[compareIndex + 1] = standard;
        }
        
        for(int i : arr) {
            System.out.print(i + " ");
        }
    }
}