挿入ソート InsertionSort

jdk8 の Arrays sort 内で使われていた Traditional（伝統的な）挿入ソート。
https://github.com/openjdk/jdk/blob/jdk8-b120/jdk/src/share/classes/java/util/DualPivotQuicksort.java#L225

www.youtube.com

シンプルな作りの中でのポイントは

• 2つの要素を比較するため、i と j の2つの変数を用意
• int ai = a[i + 1]; と2つ目の要素を保持するところからスタート（1つ目の要素は、1つ目の要素と比較しソート済みと解釈）
• ひとつ前の要素と比較し、並び替えが必要なら繰り上げを繰り返す

import java.util.Random;

public class InsertionSort {
	public static void main(String args[]) {
		//int[] a = {3,2,1};
		Random rand = new Random();
		int[] a = new int[10];
		for (int i = 0; i < a.length; i++) {
			a[i] = rand.nextInt(10) + 1;
		}
		
		System.out.println("---Before sort---");
		for (int i = 0; i < a.length; i++) {
			System.out.println(a[i]);
		}
		
		int left = 0;
		int right = a.length - 1;
		insertionSort(a, left, right);
		
		System.out.println("---After sort---");
		for (int i = 0; i < a.length; i++) {
			System.out.println(a[i]);
		}
	}

    /**
     * Sorts the specified range of the array using insertion sort.
     *
     * @param a the array to be sorted
     * @param left the index of the first element, inclusive, to be sorted
     * @param right the index of the last element, inclusive, to be sorted
     */
    private static void insertionSort(int[] a, int left, int right) {
    	for (int i = left, j = i; i < right; j = ++i) {
            int ai = a[i + 1];
            while (ai < a[j]) {
                a[j + 1] = a[j];
                if (j-- == left) {
                    break;
                }
            }
            a[j + 1] = ai;
        }
    }
}

実行結果例

---Before sort---
3
8
9
1
1
8
2
6
4
6
---After sort---
1
1
2
3
4
6
6
8
8
9