Quicksort à 3 voies, question

Question

J'essaie de comprendre le Quicksort radix à 3 voies, et je ne comprends pas pourquoi la variable CUTOFF là-bas? et la méthode d'insertion?

public class Quick3string { 

    private static final int CUTOFF = 15; // cutoff to insertion sort 

    // sort the array a[] of strings 
    public static void sort(String[] a) { 
     // StdRandom.shuffle(a); 
     sort(a, 0, a.length-1, 0); 
     assert isSorted(a); 
    } 

    // return the dth character of s, -1 if d = length of s 
    private static int charAt(String s, int d) { 
     assert d >= 0 && d <= s.length(); 
     if (d == s.length()) return -1; 
     return s.charAt(d); 
    } 


    // 3-way string quicksort a[lo..hi] starting at dth character 
    private static void sort(String[] a, int lo, int hi, int d) { 

     // cutoff to insertion sort for small subarrays 
     if (hi <= lo + CUTOFF) { 
      insertion(a, lo, hi, d); 
      return; 
     } 

     int lt = lo, gt = hi; 
     int v = charAt(a[lo], d); 
     int i = lo + 1; 
     while (i <= gt) { 
      int t = charAt(a[i], d); 
      if  (t < v) exch(a, lt++, i++); 
      else if (t > v) exch(a, i, gt--); 
      else    i++; 
     } 

     // a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]. 
     sort(a, lo, lt-1, d); 
     if (v >= 0) sort(a, lt, gt, d+1); 
     sort(a, gt+1, hi, d); 
    } 

    // sort from a[lo] to a[hi], starting at the dth character 
    private static void insertion(String[] a, int lo, int hi, int d) { 
     for (int i = lo; i <= hi; i++) 
      for (int j = i; j > lo && less(a[j], a[j-1], d); j--) 
       exch(a, j, j-1); 
    } 

    // exchange a[i] and a[j] 
    private static void exch(String[] a, int i, int j) { 
     String temp = a[i]; 
     a[i] = a[j]; 
     a[j] = temp; 
    } 

    // is v less than w, starting at character d 
    private static boolean less(String v, String w, int d) { 
     assert v.substring(0, d).equals(w.substring(0, d)); 
     return v.substring(d).compareTo(w.substring(d)) < 0; 
    } 


    // is the array sorted 
    private static boolean isSorted(String[] a) { 
     for (int i = 1; i < a.length; i++) 
      if (a[i].compareTo(a[i-1]) < 0) return false; 
     return true; 
    } 


    public static void main(String[] args) { 

     // read in the strings from standard input 
     String[] a = StdIn.readAll().split("\\s+"); 
     int N = a.length; 

     // sort the strings 
     sort(a); 

     // print the results 
     for (int i = 0; i < N; i++) 
      StdOut.println(a[i]); 
    } 
} 

de http://www.cs.princeton.edu/algs4/51radix/Quick3string.java.html

Answer 1

Il semble être utilisé pour invoquer le tri par insertion pour les tableaux suffisamment petit (taille < = 15). Ceci est le plus susceptible d'accélérer le tri.

Answer 2

C'est une optimisation simple de l'algorithme quicksort. Le coût des appels récursifs dans quicksort est assez élevé, donc pour les petits tableaux, le tri par insertion fonctionne mieux. Donc, l'idée est que si la longueur du sous-tableau à trier est inférieure à un certain seuil, il vaut mieux le trier en utilisant le tri par insertion que le tri rapide. Dans votre exemple, la variable CUTOFF définit ce seuil, c'est-à-dire si moins de 15 éléments sont laissés, ils sont triés en utilisant le tri par insertion au lieu de quicksort.

Answer 3

La méthode de tri ci-dessus est une méthode récursive. Et chaque méthode récursive devrait avoir une sorte de casse de base (sinon elle continuera à s'appeler elle-même, conduisant éventuellement à un débordement de pile). La partie d'insertion est le cas de base dans cette méthode, car à chaque étape récursive, la différence hi-lo continue de décroître, & lorsque son moins que CUTOFF, le tri d'insertion sera éventuellement déclenché, forçant la récursion à s'arrêter.

if (hi <= lo + CUTOFF) {  // base case 
    insertion(a, lo, hi, d); 
    return; 
} 

Maintenant, pourquoi l'insertion? Parce que cela fonctionne bien pour les petites baies. Plus sur le tri ici: http://www.sorting-algorithms.com/

Answer 4

Cette idée vient de Robert Sedgewick, qui en sait plus sur Quicksort que probablement tout homme vivant. Il est cité dans Donald E. Knuth, L'art de la programmation informatique, Volume III, où il montre que pour les petites M, sorte d'insertion est plus rapide que Quicksort, donc il recommande de ne pas classer les petites partitions < M du tout et en laissant à un dernier tri d'insertion sur l'ensemble des données à la fin. Knuth donne une fonction pour calculer M (qui est votre CUTOFF), et qui est 9 pour son pseudo-ordinateur MIX.