package sorting; // tri par insertion public class InsertionSort { static void insertionSort(int[] a) { for (int i = 1; i < a.length; i++) { int v = a[i], j = i; for (; 0 < j && v < a[j-1]; j--) a[j] = a[j-1]; a[j] = v; } } // trie a[l..r[ static void insertionSort(int[] a, int l, int r) { for (int i = l+1; i < r; i++) { int v = a[i], j = i; for (; l < j && v < a[j-1]; j--) a[j] = a[j-1]; a[j] = v; } } } class TestInsertionSort { static boolean is_sorted(int[] a) { for (int i = 1; i < a.length; i++) if (!(a[i - 1] <= a[i])) return false; return true; } static final int M = 10; // les éléments sont dans 0..M-1 static int[] occurrences(int[] a) { int[] occ = new int[M]; for (int i = 0; i < a.length; i++) occ[a[i]]++; return occ; } static boolean is_permut(int[] occ1, int[] occ2) { for (int i = 0; i < M; i++) if (occ1[i] != occ2[i]) return false; return true; } static String print(int[] a) { String s = "["; for (int i = 0; i < a.length; i++) s += (i == 0 ? "" : ", ") + a[i]; return s + "]"; } static int[] random_array(int len) { int[] a = new int[len]; for (int i = 0; i < len; i++) a[i] = (int) (M * Math.random()); return a; } static void test(int[] a) { System.out.println(" test avec a = " + print(a)); int[] occ1 = occurrences(a); InsertionSort.insertionSort(a); int[] occ2 = occurrences(a); System.out.println(" insertionSort(a) => a = " + print(a)); if (!is_sorted(a)) { System.out.println("ÉCHEC : le résultat n'est pas trié"); System.exit(1); } if (!is_permut(occ1, occ2)) { System.out.println("ÉCHEC : les éléments diffèrent"); System.exit(1); } } public static void main(String[] args) { System.out.println("test de insertionSort"); for (int len = 0; len < 10; len++) for (int j = 0; j <= len; j++) test(random_array(len)); System.out.println("SUCCÈS"); } }