package sorting; import java.util.Arrays; // tri rapide public class Quicksort { static void swap(int[] a, int i, int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } static int partition(int[] a, int l, int r) { // on suppose l < r i.e. au moins un élément int p = a[l], m = l; for (int i = l + 1; i < r; i++) if (a[i] < p) swap(a, i, ++m); swap(a, l, m); return m; } static void quickrec(int[] a, int l, int r) { if (r-l <= 1) return; int m = partition(a, l, r); quickrec(a, l, m); quickrec(a, m + 1, r); } static void quicksort(int[] a) { quickrec(a, 0, a.length); } /* améliorations (en exercices) * - un des deux appels récursifs remplacé par une boucle * - un mélange avant de commencer */ static void quickrec2(int[] a, int l, int r) { while (r -l > 1) { int m = partition(a, l, r); if (m - l < r - m - 1) { quickrec2(a, l, m); l = m + 1; } else { quickrec2(a, m + 1, r); r = m; } } } static void quicksort2(int[] a) { KnuthShuffle.shuffle(a); quickrec2(a, 0, a.length); } // deux améliorations de plus (en exercices) // - 3-way partition /* l lo i hi r * +------+-------+-------+-----+ * | < v | = v | ????? | > v | * +------+-------+-------+-----+ */ static void quickrec3(int[] a, int l, int r) { if (r - l <= 1) return; int p = a[l], lo = l, hi = r; // on partitionne a[l..r[ en trois for (int i = l+1; i < hi; ) { if (a[i] == p) i++; else if (a[i] < p) swap(a, i++, lo++); else // p < a[i] swap(a, i, --hi); } quickrec3(a, l, lo); quickrec3(a, hi, r); } static void quicksort3(int[] a) { KnuthShuffle.shuffle(a); quickrec3(a, 0, a.length); } // - tri par insertion sur les petits tableaux private static final int cutoff = 5; static void quickrec4(int[] a, int l, int r) { while (r - l > 1) { if (r - l < cutoff) { InsertionSort.insertionSort(a, l, r); return; } // on partitionne a[l..r[ en trois // (c'est le drapeau hollandais) int p = a[l], lo = l, hi = r; // lo i hi // ..<p.. ..=p.. ..?.. ..>p.. for (int i = l+1; i < hi; ) { if (a[i] == p) i++; else if (a[i] < p) swap(a, i++, lo++); else // p < a[i] swap(a, i, --hi); } // il faut maintenant trier a[l..lo[ et a[hi..r[ if (lo - l < r - hi) { quickrec4(a, l, lo); l = hi; } else { quickrec4(a, hi, r); r = lo; } } } static void quicksort4(int[] a) { KnuthShuffle.shuffle(a); quickrec4(a, 0, a.length); } } class TestQuicksort { 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_partition(int[] a, int l, int r) { int v = a[l]; System.out.println(" test avec a = " + print(a) + " v = " + v); int[] occ1 = occurrences(a); int m = Quicksort.partition(a, l, r); System.out.println(" partition(a," + l + "," + r + ") = " + print(a) + " m = " + m); int[] occ2 = occurrences(a); if (!is_permut(occ1, occ2)) { System.out.println("ÉCHEC : les éléments diffèrent"); System.exit(1); } for (int i = l; i < r; i++) if (!(i < m ? a[i] < v : a[i] >= v)) { System.out.println("ÉCHEC : mauvais partitionnement"); System.exit(1); } } static void test(int[] a) { System.out.println(" test avec a = " + print(a)); int[] occ1 = occurrences(a); Quicksort.quicksort3(a); int[] occ2 = occurrences(a); System.out.println(" quicksort(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) { int[] a = new int[] { 2, 5, 1, 8, 5, 3, 4 }; Quicksort.quicksort(a); System.out.println(Arrays.toString(a)); System.out.println("test de partition"); for (int len = 0; len < 10; len++) for (int l = 0; l < len; l++) for (int r = l + 1; r < len; r++) test_partition(random_array(len), l, r); System.out.println("test de quicksort"); for (int len = 0; len < 10; len++) for (int j = 0; j <= len; j++) test(random_array(len)); System.out.println("SUCCÈS"); double start = System.currentTimeMillis(); int[] large = random_array(100000000); Quicksort.quicksort4(large); System.out.println("time = " + (System.currentTimeMillis() - start)); assert is_sorted(large); } }