Insertion sort(삽입 정렬)

Insertion sort(삽입 정렬)

- 1원칙: i의 앞쪽은 이미 정렬된 상태라고 가정(i는 1부터 시작하기에 가능)

- 2원칙: i의 위치에서 자기보다 앞에 있는 (j < i)를 하나씩 비교해보며 작을경우 뒤로 Shifting한다.

- 3원칙: shifting하고 남은 공간에 i에 있던 item을 삽입한다.

i의 앞쪽은 항상 정렬된 상태이고

Best case: O() : 정렬이 거의 다 되어있는 상태에서...

Worst case: O() : 역순정렬된 상태 일때...

public class InsertionSort {

    public void sort(Comparable[] array) {

        for (int i = 1; i < array.length; i++) {

            final Comparable currentItem = array[i];

            int insertPosition = i - 1;

            while (insertPosition >= 0 && currentItem.compareTo(array[insertPosition]) < 0) {

                array[insertPosition + 1] = array[insertPosition];

                insertPosition--;

            }

            insertPosition++;

            if (insertPosition < i) {

                array[insertPosition] = currentItem;

            }

        }

    }

}

Reference:

- https://en.wikipedia.org/wiki/Insertion_sort