단순 삽입 정렬(straight insertion sort) / 셔틀 정렬(shuttle sort)

• 아직 정렬되지 않은 부분의 첫 번째 요소를 정렬된 열의 '알맞은 위치에 삽입'하는 작업을 n - 1회 반복하여 정렬하는 알고리즘
• 2번째 요소부터 선택하여 진행한다.
• 선택한 요소의 왼쪽에 이웃한 요소가 더 크면 그 값을 선택한 요소에 대입하고 앞으로 이동하면서 이 작업을 반복한다. 그러다가 선택한 요소 값 이하의 요소를 만나면 그 보다 앞쪽은 검사할 필요가 없으므로 해당 위치에 선택한 요소 값을 대입한다.
• 떨어져 있는 요소들이 서로 뒤바뀌지 않아 안정적인 알고리즘이다.
• 시간 복잡도는 O(n^2)
• 장점 : 정렬을 마쳤거나 정렬을 마친 상태에 가까우면 정렬 속도가 매우 빨라진다.
• 단점 : 삽입할 위치가 멀리 떨어져 있으면 이동(대입)해야 하는 횟수가 많아진다.

//단순 삽입 정렬
static void insertionSort(int[] a, int n) {
    for (int i = 1; i < n; i++) {
        int j;
        int tmp = a[i];        //정렬되지 않은 부분의 첫 번째 요소
        for (j = i; j > 0 && a[j - 1] > tmp; j--) {
            a[j] = a[j - 1];
        }
        a[j] = tmp;
    }
}