001// Exercise 2.2.9 2.2.20 (Solution published at http://algs4.cs.princeton.edu/) 002package algs22; 003import stdlib.*; 004/* *********************************************************************** 005 * Compilation: javac Merge.java 006 * Execution: java Merge < 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 mergesort. 012 * 013 * % more tiny.txt 014 * S O R T E X A M P L E 015 * 016 * % java Merge < tiny.txt 017 * A E E L M O P R S T X [ one string per line ] 018 * 019 * % more words3.txt 020 * bed bug dad yes zoo ... all bad yet 021 * 022 * % java Merge < words3.txt 023 * all bad bed bug dad ... yes yet zoo [ one string per line ] 024 * 025 *************************************************************************/ 026 027public class Merge { 028 029 // stably merge a[lo .. mid] with a[mid+1 .. hi] using aux[lo .. hi] 030 public static <T extends Comparable<? super T>> void merge(T[] a, T[] aux, int lo, int mid, int hi) { 031 032 // precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays 033 assert isSorted(a, lo, mid); 034 assert isSorted(a, mid+1, hi); 035 036 // copy to aux[] 037 for (int k = lo; k <= hi; k++) { 038 aux[k] = a[k]; 039 } 040 041 // merge back to a[] 042 int i = lo, j = mid+1; 043 for (int k = lo; k <= hi; k++) { 044 if (i > mid) a[k] = aux[j++]; 045 else if (j > hi) a[k] = aux[i++]; 046 else if (less(aux[j], aux[i])) a[k] = aux[j++]; 047 else a[k] = aux[i++]; 048 } 049 if (COUNT_OPS) DoublingTest.addOps (hi-lo); 050 051 // postcondition: a[lo .. hi] is sorted 052 assert isSorted(a, lo, hi); 053 } 054 055 // mergesort a[lo..hi] using auxiliary array aux[lo..hi] 056 private static <T extends Comparable<? super T>> void sort(T[] a, T[] aux, int lo, int hi) { 057 if (hi <= lo) return; 058 int mid = lo + (hi - lo) / 2; 059 sort(a, aux, lo, mid); 060 sort(a, aux, mid + 1, hi); 061 merge(a, aux, lo, mid, hi); 062 } 063 064 @SuppressWarnings("unchecked") 065 public static <T extends Comparable<? super T>> void sort(T[] a) { 066 T[] aux = (T[]) new Comparable[a.length]; 067 sort(a, aux, 0, a.length-1); 068 assert isSorted(a); 069 } 070 071 072 /* ********************************************************************* 073 * Helper sorting functions 074 ***********************************************************************/ 075 076 // is v < w ? 077 private static <T extends Comparable<? super T>> boolean less(T v, T w) { 078 if (COUNT_OPS) DoublingTest.incOps (); 079 return (v.compareTo(w) < 0); 080 } 081 082 /* ********************************************************************* 083 * Check if array is sorted - useful for debugging 084 ***********************************************************************/ 085 private static <T extends Comparable<? super T>> boolean isSorted(T[] a) { 086 return isSorted(a, 0, a.length - 1); 087 } 088 089 private static <T extends Comparable<? super T>> boolean isSorted(T[] a, int lo, int hi) { 090 for (int i = lo + 1; i <= hi; i++) 091 if (less(a[i], a[i-1])) return false; 092 return true; 093 } 094 095 096 /* ********************************************************************* 097 * Index mergesort 098 ***********************************************************************/ 099 // stably merge a[lo .. mid] with a[mid+1 .. hi] using aux[lo .. hi] 100 private static <T extends Comparable<? super T>> void merge(T[] a, int[] index, int[] aux, int lo, int mid, int hi) { 101 102 // copy to aux[] 103 for (int k = lo; k <= hi; k++) { 104 aux[k] = index[k]; 105 } 106 107 // merge back to a[] 108 int i = lo, j = mid+1; 109 for (int k = lo; k <= hi; k++) { 110 if (i > mid) index[k] = aux[j++]; 111 else if (j > hi) index[k] = aux[i++]; 112 else if (less(a[aux[j]], a[aux[i]])) index[k] = aux[j++]; 113 else index[k] = aux[i++]; 114 } 115 } 116 117 // return a permutation that gives the elements in a[] in ascending order 118 // do not change the original array a[] 119 public static <T extends Comparable<? super T>> int[] indexSort(T[] a) { 120 int N = a.length; 121 int[] index = new int[N]; 122 for (int i = 0; i < N; i++) 123 index[i] = i; 124 125 int[] aux = new int[N]; 126 indexSort(a, index, aux, 0, N-1); 127 return index; 128 } 129 130 // mergesort a[lo..hi] using auxiliary array aux[lo..hi] 131 private static <T extends Comparable<? super T>> void indexSort(T[] a, int[] index, int[] aux, int lo, int hi) { 132 if (hi <= lo) return; 133 int mid = lo + (hi - lo) / 2; 134 indexSort(a, index, aux, lo, mid); 135 indexSort(a, index, aux, mid + 1, hi); 136 merge(a, index, aux, lo, mid, hi); 137 } 138 139 // print array to standard output 140 private static <T> void show(T[] a) { 141 for (T element : a) { 142 StdOut.println(element); 143 } 144 } 145 146 // test code 147 private static boolean COUNT_OPS = false; 148 public static void main(String[] args) { 149 //String[] cards = In.readStrings ("data/cards.txt"); 150 //StdRandom.shuffle (cards); 151 152 //StdIn.fromFile ("data/tiny.txt"); 153 //StdIn.fromFile ("data/cards.txt"); 154 StdIn.fromFile ("data/words3.txt"); 155 156 String[] a = StdIn.readAllStrings(); 157 sort(a); 158 show(a); 159 160 COUNT_OPS = true; 161 DoublingTest.run (20000, 5, N -> ArrayGenerator.integerRandomUnique (N), (Integer[] x) -> sort (x)); 162 DoublingTest.run (20000, 5, N -> ArrayGenerator.integerRandom (N, 2), (Integer[] x) -> sort (x)); 163 DoublingTest.run (20000, 5, N -> ArrayGenerator.integerPartiallySortedUnique (N), (Integer[] x) -> sort (x)); 164 } 165}