001// Exercise 2.2.11 (Solution published at http://algs4.cs.princeton.edu/) 002package algs22; 003import stdlib.*; 004/* *********************************************************************** 005 * Compilation: javac MergeX.java 006 * Execution: java MergeX < input.txt 007 * Dependencies: StdOut.java StdIn.java 008 * Data files: http://algs4.cs.princeton.edu/22merge/tiny.txt 009 * http://algs4.cs.princeton.edu/22merge/words3.txt 010 * 011 * Sorts a sequence of strings from standard input using an 012 * optimized version of mergesort. 013 * 014 * % more tiny.txt 015 * S O R T E X A M P L E 016 * 017 * % java MergeX < tiny.txt 018 * A E E L M O P R S T X [ one string per line ] 019 * 020 * % more words3.txt 021 * bed bug dad yes zoo ... all bad yet 022 * 023 * % java MergeX < words3.txt 024 * all bad bed bug dad ... yes yet zoo [ one string per line ] 025 * 026 *************************************************************************/ 027 028public class XMergeX { 029 private static final int CUTOFF = 7; // cutoff to insertion sort 030 031 032 private static <T extends Comparable<? super T>> void merge(T[] src, T[] dst, int lo, int mid, int hi) { 033 034 // precondition: src[lo .. mid] and src[mid+1 .. hi] are sorted subarrays 035 assert isSorted(src, lo, mid); 036 assert isSorted(src, mid+1, hi); 037 038 int i = lo, j = mid+1; 039 for (int k = lo; k <= hi; k++) { 040 if (i > mid) dst[k] = src[j++]; 041 else if (j > hi) dst[k] = src[i++]; 042 else if (less(src[j], src[i])) dst[k] = src[j++]; // to ensure stability 043 else dst[k] = src[i++]; 044 } 045 if (COUNT_OPS) DoublingTest.addOps (hi-lo); 046 047 // postcondition: dst[lo .. hi] is sorted subarray 048 assert isSorted(dst, lo, hi); 049 } 050 051 private static <T extends Comparable<? super T>> void sort(T[] src, T[] dst, int lo, int hi) { 052 if (hi <= lo + CUTOFF) { 053 insertionSort(src, lo, hi); 054 return; 055 } 056 int mid = lo + (hi - lo) / 2; 057 sort(dst, src, lo, mid); 058 sort(dst, src, mid+1, hi); 059 060 /* 061 if (!less(dst[mid+1], dst[mid])) { 062 for (int i = lo; i <= hi; i++) src[i] = dst[i]; 063 return; 064 } 065 */ 066 // a bit faster 067 if (!less(dst[mid+1], dst[mid])) { 068 System.arraycopy(dst, lo, src, lo, hi - lo + 1); 069 return; 070 } 071 072 merge(dst, src, lo, mid, hi); 073 } 074 075 public static <T extends Comparable<? super T>> void sort(T[] a) { 076 /* 077 Comparable[] aux = new Comparable[a.length]; 078 for (int i = 0; i < a.length; i++) 079 aux[i] = a[i]; 080 */ 081 // a bit faster 082 T[] aux = a.clone(); 083 sort(a, aux, 0, a.length-1); 084 085 assert isSorted(a); 086 } 087 088 089 // sort from a[lo] to a[hi] using insertion sort 090 private static <T extends Comparable<? super T>> void insertionSort(T[] a, int lo, int hi) { 091 for (int i = lo; i <= hi; i++) 092 for (int j = i; j > lo && less(a[j], a[j-1]); j--) 093 exch(a, j, j-1); 094 } 095 096 097 // exchange a[i] and a[j] 098 private static <T> void exch(T[] a, int i, int j) { 099 if (COUNT_OPS) DoublingTest.incOps (); 100 T swap = a[i]; 101 a[i] = a[j]; 102 a[j] = swap; 103 } 104 105 // is a[i] < a[j]? 106 private static <T extends Comparable<? super T>> boolean less(T a, T b) { 107 if (COUNT_OPS) DoublingTest.incOps (); 108 return (a.compareTo(b) < 0); 109 } 110 111 /* ********************************************************************* 112 * Check if array is sorted - useful for debugging 113 ***********************************************************************/ 114 private static <T extends Comparable<? super T>> boolean isSorted(T[] a) { 115 return isSorted(a, 0, a.length - 1); 116 } 117 118 private static <T extends Comparable<? super T>> boolean isSorted(T[] a, int lo, int hi) { 119 for (int i = lo + 1; i <= hi; i++) 120 if (less(a[i], a[i-1])) return false; 121 return true; 122 } 123 124 // print array to standard output 125 private static <T> void show(T[] a) { 126 for (T element : a) { 127 StdOut.println(element); 128 } 129 } 130 131 // test code 132 private static boolean COUNT_OPS = false; 133 public static void main(String[] args) { 134 StdIn.fromFile ("data/words3.txt"); 135 String[] a = StdIn.readAllStrings(); 136 sort(a); 137 show(a); 138 139 COUNT_OPS = true; 140 DoublingTest.run (20000, 5, N -> ArrayGenerator.integerRandomUnique (N), (Integer[] x) -> sort (x)); 141 DoublingTest.run (20000, 5, N -> ArrayGenerator.integerRandom (N, 2), (Integer[] x) -> sort (x)); 142 DoublingTest.run (20000, 5, N -> ArrayGenerator.integerPartiallySortedUnique (N), (Integer[] x) -> sort (x)); 143 144 } 145}