package sorting; // tri par tas public class Heapsort { // recursive version of moveDown static void moveDownRec(int[] a, int k, int v, int n) { int r = 2 * k + 1; if (r >= n) a[k] = v; else { if (r + 1 < n && a[r] < a[r + 1]) r++; if (a[r] <= v) a[k] = v; else { a[k] = a[r]; moveDownRec(a, r, v, n); } } } static void moveDown(int[] a, int i, int x, int n) { while (true) { int j = 2 * i + 1; if (j >= n) break; if (j + 1 < n && a[j] < a[j + 1]) j++; if (a[j] <= x) break; a[i] = a[j]; i = j; } a[i] = x; } static void heapsort(int[] a) { int n = a.length; for (int k = n / 2 - 1; k >= 0; k--) moveDown(a, k, a[k], n); for (int k = n - 1; k >= 1; k--) { int v = a[k]; a[k] = a[0]; moveDown(a, 0, v, k); } } } class TestHeapsort { 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); Heapsort.heapsort(a); int[] occ2 = occurrences(a); System.out.println(" heapsort(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 mergesort"); for (int len = 0; len < 10; len++) for (int j = 0; j <= len; j++) test(random_array(len)); System.out.println("SUCCÈS TestHeapsort"); } }