Java - Data structures

P2 (35 points)

You can sort a large array of m integers that are in the range 1 to n by using an array count of n entries to count the number of occurrences of each integer in the array. For example, consider the following array A of 14 integers that are in the range from 1 to 9 (note that in this case m = 14 and n = 9):

9 2 4 8 9 4 3 2 8 1 2 7 2 5

Form an array count of 9 elements such that count[i-1] contains the number of times that i occurs in the array to be sorted. Thus, count is

1 4 1 2 1 0 1 2 2

In particular, count[0] = 1 since 1 occurs once in A. count[1] = 4 since 2 occurs 4 times in A. count[2]=1 since 3 occurs once in A. count[3] =2 since 4 occurs 2 times in A.

Use the count array to sort the original array A. Implement this sorting algorithm in the function

public static void countingSort(int[] a, int n )

and analyze its worst case running time in terms of m (the length of array a) and n.

After calling countingSort(), a must be a sorted array (do not store sorting result in a temporary array).

ArraySort.java

public class ArraySort { public static > void mergeSort(T[] a, T[] tempArray, int first, int last) { if (first < last) { // sort each half int mid = (first + last) / 2;// index of midpoint mergeSort(a, first, mid); // sort left half array[first..mid] mergeSort(a, mid + 1, last); // sort right half array[mid+1..last] if (a[mid].compareTo(a[mid + 1]) > 0) merge(a, tempArray, first, mid, last); // merge the two halves // else skip merge step } } private static > void merge(T[] a, T[] tempArray, int first, int mid, int last) { // Two adjacent subarrays are a[beginHalf1..endHalf1] and a[beginHalf2..endHalf2]. int beginHalf1 = first; int endHalf1 = mid; int beginHalf2 = mid + 1; int endHalf2 = last; // while both subarrays are not empty, copy the // smaller item into the temporary array int index = beginHalf1; // next available location in // tempArray for (; (beginHalf1 <= endHalf1) && (beginHalf2 <= endHalf2); index++) { if (a[beginHalf1].compareTo(a[beginHalf2]) < 0) { tempArray[index] = a[beginHalf1]; beginHalf1++; } else { tempArray[index] = a[beginHalf2]; beginHalf2++; } } // finish off the nonempty subarray // finish off the first subarray, if necessary for (; beginHalf1 <= endHalf1; beginHalf1++, index++) tempArray[index] = a[beginHalf1]; // finish off the second subarray, if necessary for (; beginHalf2 <= endHalf2; beginHalf2++, index++) tempArray[index] = a[beginHalf2]; // copy the result back into the original array for (index = first; index <= last; index++) a[index] = tempArray[index]; } // Quick Sort // Median-of-three privot selection // Sort by comparison private static > void sortFirstMiddleLast(T[] a, int first, int mid, int last) { // Note similarity to bubble sort order(a, first, mid); // make a[first] <= a[mid] order(a, mid, last); // make a[mid] <= a[last] order(a, first, mid); // make a[first] <= a[mid] }

private static > void order(T[] a, int i, int j) { if (a[i].compareTo(a[j]) > 0) swap(a, i, j); } private static void swap(Object[] array, int i, int j) { Object temp = array[i]; array[i] = array[j]; array[j] = temp; } // Partitioning private static > int partition(T[] a, int first, int last) { int mid = (first + last)/2; sortFirstMiddleLast(a, first, mid, last);

// move pivot to next-to-last position in array swap(a, mid, last - 1); int pivotIndex = last - 1; T pivot = a[pivotIndex];

// determine subarrays Smaller = a[first..endSmaller] // and Larger = a[endSmaller+1..last-1] // such that entries in Smaller are <= pivot and // entries in Larger are >= pivot; initially, these subarrays are empty int indexFromLeft = first + 1; int indexFromRight = last - 2; boolean done = false; while (!done) { // starting at beginning of array, leave entries that are < pivot; // locate first entry that is >= pivot; you will find one, // since last entry is >= pivot while (a[indexFromLeft].compareTo(pivot) < 0) indexFromLeft++; // starting at end of array, leave entries that are > pivot; // locate first entry that is <= pivot; you will find one, // since first entry is <= pivot while (a[indexFromRight].compareTo(pivot) > 0) indexFromRight--; if (indexFromLeft < indexFromRight) { swap(a, indexFromLeft, indexFromRight); indexFromLeft++; indexFromRight--; } else done = true; } // end while // place pivot between Smaller and Larger subarrays swap(a, pivotIndex, indexFromLeft); pivotIndex = indexFromLeft; return pivotIndex; } public static > void quickSort(T[] a, int n) { quickSort(a, 0, n - 1); } public static > void quickSort(T[] a, int first, int last) { // perform recursive step if 2 or more elements if(first < last) { // create the partition: Smaller | Pivot | Larger int pivotIndex = partition(a, first, last); // sort subarrays Smaller and Larger quickSort(a, first, pivotIndex - 1); quickSort(a, pivotIndex + 1, last); } } }