3 vías clasificación rápida, pregunta

Question

Estoy tratando de comprender el 3 vías Radix ordenación rápida, y yo no entiendo por qué la variable de la CORTE allí? y el método de inserción?

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]);
    }
}

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

Answer 1

Al parecer, para ser utilizado con el fin de inserción invoke tipo para suficientemente pequeño (tamaño <= 15) arrays. Esto es más probable para acelerar la clasificación.

Answer 2

Es una optimización sencilla del algoritmo de ordenación rápida. El coste de las llamadas recursivas en la clasificación rápida son bastante alto, por lo que para las pequeñas matrices de ordenación por inserción funciona mejor. Por lo tanto, la idea es que si la longitud de la subserie sea OS ordenada por debajo de cierto umbral, que es mejor para solucionar el problema mediante la inserción tipo de ordenación rápida. En su ejemplo, define variables de corte que umbral, es decir, si menos de 15 elementos se dejan, se ordenan usando la ordenación por inserción en lugar de quicksort.

Answer 3

El método para ordenar anteriormente es un método recursivo. Y cada método recursivo debe tener algún tipo de caso base (de lo contrario, seguir llamando a sí mismo, llevando eventualmente a un desbordamiento de pila).

La parte de inserción es el caso base en ese método, porque a cada paso recursivo, la diferencia Hi-Lo sigue disminuyendo, y cuando su menos de corte, con el tiempo se activará el tipo de inserción, obligando a la recursividad de parada.

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

Ahora, la razón por la inserción? Debido a que funciona bien para los pequeños arreglos. Más en la clasificación aquí: http://www.sorting-algorithms.com/

Answer 4

Esta idea proviene de Robert Sedgewick, que sabe más sobre la ordenación rápida que probablemente cualquier hombre vivo. Es citado en Donald E. Knuth, The Art of Computer Programming, Volumen III, donde se muestra que para las pequeñas M, ordenación por inserción es más rápida que la ordenación rápida, por lo que recomienda no clasificar pequeñas particiones < M en absoluto y dejando a uno inserción final especie en todo el conjunto de datos al final. Knuth da una función de cálculo de M (que es su CUTOFF), y que es 9 por su MIX pseudo-ordenador.