001package algs23; 002import stdlib.*; 003/* *********************************************************************** 004 * Compilation: javac QuickDualPivot.java 005 * Execution: java QuickDualPivot < input.txt 006 * Dependencies: StdOut.java StdIn.java 007 * Data files: http://algs4.cs.princeton.edu/23quicksort/tiny.txt 008 * http://algs4.cs.princeton.edu/23quicksort/words3.txt 009 * 010 * Sorts a sequence of strings from standard input using dual-pivot 011 * quicksort. 012 * 013 * [Warning: not thoroughly tested.] 014 * 015 * % more tiny.txt 016 * S O R T E X A M P L E 017 * 018 * % java QuickDualPivot < tiny.txt 019 * A E E L M O P R S T X [ one string per line ] 020 * 021 * % more words3.txt 022 * bed bug dad yes zoo ... all bad yet 023 * 024 * % java QuickDualPivot < words3.txt 025 * all bad bed bug dad ... yes yet zoo [ one string per line ] 026 * 027 *************************************************************************/ 028 029public class XQuickDualPivot { 030 031 // quicksort the array a[] using dual-pivot quicksort 032 public static <T extends Comparable<? super T>> void sort(T[] a) { 033 sort(a, 0, a.length - 1); 034 assert isSorted(a); 035 } 036 037 // quicksort the subarray a[lo .. hi] using dual-pivot quicksort 038 private static <T extends Comparable<? super T>> void sort(T[] a, int lo, int hi) { 039 if (hi <= lo) return; 040 041 // make sure a[lo] <= a[hi] 042 if (less(a[hi], a[lo])) exch(a, lo, hi); 043 044 int lt = lo + 1, gt = hi - 1; 045 int i = lo + 1; 046 while (i <= gt) { 047 if (less(a[i], a[lo])) exch(a, lt++, i++); 048 else if (less(a[hi], a[i])) exch(a, i, gt--); 049 else i++; 050 } 051 exch(a, lo, --lt); 052 exch(a, hi, ++gt); 053 054 // recursively sort three subarrays 055 sort(a, lo, lt-1); 056 if (less(a[lt], a[gt])) sort (a, lt+1, gt-1); 057 sort(a, gt+1, hi); 058 059 assert isSorted(a, lo, hi); 060 } 061 062 063 064 /* ********************************************************************* 065 * Helper sorting functions 066 ***********************************************************************/ 067 068 // is v < w ? 069 private static <T extends Comparable<? super T>> boolean less(T v, T w) { 070 return (v.compareTo(w) < 0); 071 } 072 073 // exchange a[i] and a[j] 074 private static void exch(Object[] a, int i, int j) { 075 Object swap = a[i]; 076 a[i] = a[j]; 077 a[j] = swap; 078 } 079 080 /* ********************************************************************* 081 * Check if array is sorted - useful for debugging 082 ***********************************************************************/ 083 private static <T extends Comparable<? super T>> boolean isSorted(T[] a) { 084 return isSorted(a, 0, a.length - 1); 085 } 086 087 private static <T extends Comparable<? super T>> boolean isSorted(T[] a, int lo, int hi) { 088 for (int i = lo + 1; i <= hi; i++) 089 if (less(a[i], a[i-1])) return false; 090 return true; 091 } 092 093 094 095 // print array to standard output 096 private static <T> void show(T[] a) { 097 for (T element : a) { 098 StdOut.println(element); 099 } 100 } 101 102 // Read strings from standard input, sort them, and print. 103 public static void main(String[] args) { 104 String[] a = StdIn.readAllStrings(); 105 sort(a); 106 show(a); 107 } 108 109}