[Java] 삽입정렬 Insertion Sort

삽입정렬 - 현재 위치에서 그 이하의 배열들을 비교하여 자신이 들어갈 위치를 찾아 삽입하는 방법

최악의 경우 : 역순으로 정렬되어 있는 경우

평균 시간 복잡도 O(n^2)

public static void insertionSort(int[] numbers) {
        int i, j;
        for (i = 1; i < numbers.length; i++ ) {
            int tmp = numbers[i];
            for (j = i; j > 0; j--) {
                if (numbers[j-1] > tmp) {
                    numbers[j] = numbers[j-1];
                    numbers[j-1] = tmp;
                }
            }    
        }
}

중간에 원소를 삽입하면 그 뒤에 있는 모든 원소를 한칸씩 뒤로 이동시켜야 한다.

몇백만개의 원소가 있는 배열이라면 이런 부분은 큰 부담이다.

=>LinkedList를 사용

public static List<Integer> insertSort(final List<Integer> numbers) {
        final List<Integer> insertList = new LinkedList<>();
        
        original : for (Integer number : numbers) {
            for (int i = 0; i < insertList.size(); i++) {
                if (number < insertList.get(i)) {
                    insertList.add(i, number);
                    continue original;
                }
            }
            insertList.add(insertList.size(), number);
        }
        
        return insertList;
    }