3-way quicksort question

Question

I am trying to understand the 3-way radix Quicksort and I do not understand why the CUTOFF variable exists? and insert method?

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

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

Answer 1

It is apparently used to invoke insertion sorting for fairly small (size <= 15) arrays. Most likely, this will speed up the sorting.

Answer 2

This is a simple optimization of the quick sort algorithm. The cost of recursive calls in quicksort is quite high, so it’s better to work with sorting small arrays. So the idea is that if the length of the subarray should be os sorted below a certain threshold, it is better to sort it using insertion sort than quicksort. In your example, the CUTOFF variable defines this threshold, i.e. If less than 15 items are left, they are sorted using insertion sort instead of quick sort.

Answer 3

The sorting method above is a recursive method. And each recursive method must have some basic case (otherwise it will continue to call itself, which will ultimately lead to a stack overflow).

The input part is the basic argument in this method because at each recursive step the hi-lo difference continues to decrease, and when it is less than CUTOFF, insertion sorting will ultimately be called, causing the recursion to stop.

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

Now, why embed? Because it works well for small arrays. More on sorting here: http://www.sorting-algorithms.com/

Answer 4

This idea comes from Robert Sedgewick, who knows more about Quicksort than probably any person. He is quoted in Donald E. Knuth’s book, “The Art of Computer Programming,” Volume III, where he shows that for small M sorts inserts are faster than Quicksort, so he recommends not sorting small sections <M and leaving it to one final sort all over dataset at the end. Knuth provides a function for calculating M (this is your CUTOFF ), and for his pseudo-computer MIX - 9.