In JAVA; create an array of names. Display the names in UNSORTED order. Apply th
ID: 3667762 • Letter: I
Question
In JAVA; create an array of names. Display the names in UNSORTED order. Apply the Mergsort and Display the names in SORTED order.
public class TestMerge {
public static void main (String [ ] args ) {
***Create your array of Strings with AT LEAST 5 names
System.out.println ( " ____________________________");
***LOOP through your array and print out each UNSORTED string
System.out.println ( " ____________________________");
Merge.sort (words);
***LOOP through your array and print out each SORTED string
System.out.println ( " ____________________________");
}
}
Output:
Hank
Jim
Aaron
Brian
Dan
__________
Aaron
Brian
Dan
Hank
Jim
Merg.sort funtion:
import edu.princeton.cs.algs4.StdOut;
public class Merge {
// This class should not be instantiated.
private Merge() { }
// stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi]
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
// precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays
assert isSorted(a, lo, mid);
assert isSorted(a, mid+1, hi);
// copy to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
// merge back to a[]
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
// postcondition: a[lo .. hi] is sorted
assert isSorted(a, lo, hi);
}
// mergesort a[lo..hi] using auxiliary array aux[lo..hi]
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid + 1, hi);
merge(a, aux, lo, mid, hi);
}
/**
* Rearranges the array in ascending order, using the natural order.
* @param a the array to be sorted
*/
public static void sort(Comparable[] a) {
Comparable[] aux = new Comparable[a.length];
sort(a, aux, 0, a.length-1);
assert isSorted(a);
}
/***************************************************************************
* Helper sorting functions.
***************************************************************************/
// is v < w ?
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
Object swap = a[i];
a[i] = a[j];
a[j] = swap;
}
/***************************************************************************
* Check if array is sorted - useful for debugging.
***************************************************************************/
private static boolean isSorted(Comparable[] a) {
return isSorted(a, 0, a.length - 1);
}
private static boolean isSorted(Comparable[] a, int lo, int hi) {
for (int i = lo + 1; i <= hi; i++)
if (less(a[i], a[i-1])) return false;
return true;
}
/***************************************************************************
* Index mergesort.
***************************************************************************/
// stably merge a[lo .. mid] with a[mid+1 .. hi] using aux[lo .. hi]
private static void merge(Comparable[] a, int[] index, int[] aux, int lo, int mid, int hi) {
// copy to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = index[k];
}
// merge back to a[]
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if (i > mid) index[k] = aux[j++];
else if (j > hi) index[k] = aux[i++];
else if (less(a[aux[j]], a[aux[i]])) index[k] = aux[j++];
else index[k] = aux[i++];
}
}
/**
* Returns a permutation that gives the elements in the array in ascending order.
* @param a the array
* @return a permutation <tt>p[]</tt> such that <tt>a[p[0]]</tt>, <tt>a[p[1]]</tt>,
* ..., <tt>a[p[N-1]]</tt> are in ascending order
*/
public static int[] indexSort(Comparable[] a) {
int N = a.length;
int[] index = new int[N];
for (int i = 0; i < N; i++)
index[i] = i;
int[] aux = new int[N];
sort(a, index, aux, 0, N-1);
return index;
}
// mergesort a[lo..hi] using auxiliary array aux[lo..hi]
private static void sort(Comparable[] a, int[] index, int[] aux, int lo, int hi) {
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, index, aux, lo, mid);
sort(a, index, aux, mid + 1, hi);
merge(a, index, aux, lo, mid, hi);
}
// print array to standard output
private static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
StdOut.println(a[i]);
}
}
}
Explanation / Answer
public static void mergeSort(String[] names)
{
if (names.length >= 2)
{
String[] left = new String[names.length/2];
String[] right = new String[names.length-names.length/2];
for (int i = 0; i < left.length; i++)
{
left[i] = names[i];
}
for (int i = 0; i < right.length; i++)
{
right[i] = names[i + names.length/2];
}
mergeSort(left);
mergeSort(right);
merge(names, left, right);
}
}
// pre : result is empty; list1 is sorted; list2 is sorted
// post: result contains result of merging sorted lists;
// add merge method below
public static void merge(String[] names, String[] left, String[] right)
{
int i1 = 0;
int i2 = 0;
for (int i = 0; i < names.length; i++)
{
if (i2 >= right.length || (i1 < left.length && left[i1].compareToIgnoreCase(right[i1])<0))
{
names[i] = left[i1];
i1++;
} else
{
names[i] = right[i2];
i2++;
}
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.