「アルゴリズム」逆配列、ソートと挿入ソートのどちらが速いかを選択

2.1.6すべてのプライマリ・キーが同じ場合、ソートと挿入ソートのどちらが速いかを選択します.
ソートの挿入が高速
2.1.7逆順配列の場合、ソートと挿入ソートのどちらが速いかを選択します.
より高速なソートの選択
どうして?コードを見てから説明します
一、並べ替えのコードを挿入する

package test;

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;

public class Insertion {
	public static void sort(Comparable[] a){
		for(int i=1; i0 && less(a[j], a[j-1]); j--){
				exch(a, j, j-1);
			}
		}
	}
	
	private static boolean less(Comparable v, Comparable w){
		return v.compareTo(w) < 0;
	}
	
	private static void exch(Comparable[] a, int i, int j){
		Comparable t = a[i];
		a[i] = a[j];
		a[j] = t;
	}
	
	private static void show(Comparable[] a){
		for(int i=0; i

二、ソートコードの選択

package test;

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;

public class Selection {
	public static void sort(Comparable[] a){
		int N = a.length;
		for(int i=0; i

三、アルゴリズム時間比較のコード

package test;

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.Stopwatch;

public class SortCompare {
	public static double time(String alg, Double[] a){
		Stopwatch timer = new Stopwatch();
		if(alg.equals("Insertion")) Insertion.sort(a);
		if(alg.equals("Selection")) Selection.sort(a);
		/*if(alg.equals("Shell")) Shell.sort(a);
		if(alg.equals("Merge")) Merge.sort(a);
		if(alg.equals("Quick")) Quick.sort(a);
		if(alg.equals("Heap")) Heap.sort(a);*/
		return timer.elapsedTime();
	}
	
	public static double timeRandomInput(String alg, int N, int T){
		//    alg， T    N       ，     
		double total = 0.0;
		Double[] a = new Double[N];
		for(int t = 0; t < T; t++){
			//      （         ）
			for(int i=0; i

四、運行
アルゴリズム時間比較のコードSortCompare.JAvaの比較
コンソール入力:Insertion Selection 1000 100
出力結果(パソコンごとに、毎回結果が違うので、慌てないでください):
Insertion Selection 1000 100 for 1000 random Doules   Insertion is 1.3 times faster than Selection for 1000 equal Doules   Insertion is 213.0 times faster than Selection for 1000 inverse Doules   Insertion is 0.9 times faster than Selection
五、解釈
1、なぜすべてのプライマリ・キーが同時に挿入され、ソートが速くなるのですか?
配列要素は同じです
挿入ソート、比較回数N-1、交換回数0
ソート選択、比較回数N(N-1)/2、交換回数0
2、逆配列の場合、ソートを選択する方が早いのはなぜですか?
配列逆シーケンス時
挿入ソートは,逆シーケンス対にN(N−1)/2対があるため,交換回数はN(N−1)/2である.比較回数が交換回数以上、以下
交換回数+N-1.
ソートを選択し,入力がどうであれ比較回数はN(N−1)/2である.このときの交換回数はN−1である.