Question

1 Approved Answer

Posted on Sep 22, 2024

The formula: (last first + 1) represents the number of elements the partition method is to work with. For arrays that are fewer than 7

The formula: (last first + 1) represents the number of elements the partition method is to work with. For arrays that are fewer than 7 (MIN_SIZE) entries, quickSort calls insertionSort method right away, so partition method is not called.

You need to revise the implementation of partition method in SortArray.java as described below:

if we have exactly 7 elements, choose the current middle entry for the pivot

else if we have between 8 and 40 elements inclusive, use the median-of-three pivot selection scheme

else (we have more than 40 elements), the pivot should be the median-of-nine entries that are about equally spaced, including the first, last, and middle entries. See the median-of-nine pivot selection algorithm below.

The median-of-nine pivot selection algorithm:

first identify the nine indexes

must be implemented as a recursive method called findNineCandidatePivotIndexes

the methods parameter called indexes should contain the list of 9 indexes once the method is finished.

sort the calculated indexes with Collections.sort method. For example, you should see the following content in the indexes list:

for array of size 41 the indexes would be: 0, 5, 10, 15, 20, 25, 30, 35, 40

for array of size 50 the indexes would be: 0, 6, 12, 18, 24, 30, 36, 42, 49

for array of size 67 the indexes would be: 0, 8, 16, 24, 33, 41, 49, 57, 66

for array of size 72 the indexes would be: 0, 8, 17, 26, 35, 44, 53, 62, 71

for array of size 100 the indexes would be: 0, 12, 24, 36, 49, 61, 74, 86, 99

after the indexes have been sorted:

sort the nine elements at those indexes using insertion sort algorithm (implement and call method insertionSortNinePivotIndexes)

select the element at the middle index to be the pivot

after the pivot selection, the partition algorithm will follow the same flow as with the median-of-three

import java.util.ArrayList; public class SortArray { /**************************************************************  * ITERATIVE SELECTION SORT  **************************************************************/   /**  * Task: Sorts the first n objects in an array into ascending order.  *  * @param a an array of Comparable objects  * @param n an integer > 0  */  public static mergeSort(a, tempArray, first, last); } // end mergeSort /**  * Task: recursively merge sort a portion of an array.  *  * @param a an array of Comparable objects  * @param tempArray an array used by the merge step  * @param first an integer >= 0 that is the index of the first  * array element to consider  * @param last an integer >= 0 that is the index of the last  * array element to consider  */  private static > void mergeSort(T[] a, T[] tempArray, int first, int last) { if (last > first) // we have some work to do { int mid = (last + first) / 2; mergeSort(a, tempArray, first, mid); mergeSort(a, tempArray, mid + 1, last); merge(a, tempArray, first, mid + 1, last); } } // end mergeSort /**  * Task: Merge the elements in two contiguous sorted sublists  *  * @param a an array of Comparable objects  * @param tempArray a temporay array used in the merge  * @param first an integer >= 0 and < mid  * @param mid an integer <= last  * @param last an integer < a.length  */  private static > void merge(T[] a, T[] tempArray, int first, int mid, int last) { int beginHalf1 = first; int endHalf1 = mid - 1; int beginHalf2 = mid; int endHalf2 = last; // While both subarrays are not empty, compare an element in one subarray with //an element in the other; then copy the smaller item into the temporary array int index = first; //next available location in tempArray while ((beginHalf1 <= endHalf1) && (beginHalf2 <= endHalf2)) { if (a[beginHalf1].compareTo(a[beginHalf2]) < 0) { tempArray[index] = a[beginHalf1]; beginHalf1++; } else { tempArray[index] = a[beginHalf2]; beginHalf2++; } index++; } //Assertion: One subarray has been completely copied to tempArray. // copy any remaining values from the first subarray over to temp while (beginHalf1 <= endHalf1) tempArray[index++] = a[beginHalf1++]; // copy any remaining values from the second subarray over to temp while (beginHalf2 <= endHalf2) tempArray[index++] = a[beginHalf2++]; // copy values back for (int i = first; i <= last; i++) { a[i] = tempArray[i]; } } // end merge /**  * ***********************************************************  * QUICK SORT -  * RECURSIVE  * MEDIAN OF THREE  * DOES INSERTION SORT ON SMALL ARRAYS  * ************************************************************  */   private static int MIN_SIZE = 7; /**  * Task: Sorts the first n objects in an array into ascending order.  *  * @param a an array of Comparable objects  * @param n an integer > 0  */  public static > void quickSort(T[] a, int n) { quickSort(a, 0, n - 1); } /**  * Task: Recursively sorts an array into ascending order. Uses quick sort with  * median-of-three pivot selection for arrays of at least  * MIN_SIZE elements, and uses insertion sort for other arrays.  *  * @param a an array of Comparable objects  * @param first an integer >= 0 that is the index of the first  * array element to consider  * @param last an integer >= 0 that is the index of the last  * array element to consider  */  private static > void quickSort(T[] a, int first, int last) { if (last - first + 1 < MIN_SIZE) { insertionSort(a, first, last); } else { // 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); } } /**  * Task: Sorts the first, middle, and last elements of an  * array into ascending order.  *  * @param a an array of Comparable objects  * @param first the integer index of the first array element; first >= 0  * @param mid the integer index of the middle array element  * @param last the integer index of the last array element;  * last - first >= 2, last < a.length  */  private static > void sortFirstMiddleLast(T[] a, int first, int mid, int last) { orderTwoItems(a, first, mid); // make a[first] <= a[mid] orderTwoItems(a, mid, last); // make a[mid] <= a[last] orderTwoItems(a, first, mid); // make a[first] <= a[mid] } // end sortFirstMiddleLast /**  * Task: Orders two given array elements into ascending order  * so that a[i] <= a[j].  *  * @param a an array of Comparable objects  * @param i an integer >= 0 and < array.length  * @param j an integer >= 0 and < array.length  */  private static > void orderTwoItems(T[] a, int i, int j) { if (a[i].compareTo(a[j]) > 0) swap(a, i, j); } // end orderTwoItems /**  * Finds recursively indexes of nine pivot candidates  *  * @param indexes indexes of pivot candidates  * @param a an array of Comparable objects  * @param first the integer index of the first sub-array element  * @param mid the integer index of the middle sub-array element  * @param last the integer index of the last sub-array element  * @param size number of elements in the sub-array  */  private static > void findNineCandidatePivotIndexes(ArrayList indexes, T[] a, int first, int mid, int last, int size) { //TODO Project 4  final int NUMBER_OF_SUB_ARRAYS = 8; // IMPLEMENT this method recursively } /**  * Performs insertion sort on nine pivot candidates  * @param indexes indexes of pivot candidates  * @param a an array of Comparable objects  */  private static > void insertionSortNinePivotCandidates(ArrayList indexes, T[] a) { //TODO Project 4  // follow insertion sort algorithm } /**  * Task: Partitions an array as part of quick sort into two subarrays  * called Smaller and Larger that are separated by a single  * element called the pivot.  * Elements in Smaller are left of the pivot and <= pivot.  * Elements in Larger are right of the pivot and >= pivot.  *  * @param a an array of Comparable objects  * @param first the integer index of the first array element;  * first >= 0  * @param last the integer index of the last array element;  * last >= first; last < a.length  * @return the index of the pivot  */  private static > int partition(T[] a, int first, int last) { //TODO Project 4  // modify this code per lab description int mid = first + (last - first) / 2; sortFirstMiddleLast(a, first, mid, last); int pivotIndex = mid; if (last - first + 1 > 3) { // Move pivot to next-to-last position in array swap(a, mid, last - 1); pivotIndex = last - 1; } // done choosing pivot // at this point pivot is moved to the appropriate spot in the array if (last - first + 1 > 3) { T pivotValue = a[pivotIndex]; // Determine subarrays Smaller = a[first..endSmaller] // and Larger = a[endSmaller+1..last-1] // such that entries in Smaller are <= pivotValue and // entries in Larger are >= pivotValue; 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 < pivotValue; // locate first entry that is >= pivotValue; you will find one, // since last entry is >= pivot while (a[indexFromLeft].compareTo(pivotValue) < 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(pivotValue) > 0) indexFromRight--; assert a[indexFromLeft].compareTo(pivotValue) >= 0 && a[indexFromRight].compareTo(pivotValue) <= 0; if (indexFromLeft < indexFromRight) { swap(a, indexFromLeft, indexFromRight); indexFromLeft++; indexFromRight--; } else done = true; } // Place pivotValue between the subarrays Smaller and Larger swap(a, pivotIndex, indexFromLeft); pivotIndex = indexFromLeft; // Assertion: // Smaller = a[first..pivotIndex-1] // Pivot = a[pivotIndex] // Larger = a[pivotIndex+1..last] } return pivotIndex; } // end partition /**************************************************************  *  * COUNTING SORT  *  **************************************************************/  /**  * Making only one pass through the array, counts the number of times  * each integer occurs in the array. These counts are then used  * to sort the array  *  * @param a array to be sorted  * @param maxValue the maximum possible value in the array  */  public static void countingSort(int[] a, int maxValue) { int N = a.length; if (N == 0) return; int[] count = new int[maxValue + 1]; /** make count/frequency array for each element **/   for (int i = 0; i < N; i++) count[a[i]]++; /** modify count so that positions in final array is obtained **/   for (int i = 1; i <= maxValue; i++) count[i] += count[i - 1]; /** modify original array **/   int j = 0; for (int i = 0; i < maxValue; i++) while (j < count[i]) a[j++] = i; //TODO Project 2   } // end countingSort /**************************************************************  *  * BINARY RADIX SORT  *  **************************************************************/   /**  * Utilizing radix sort algorithm sorts the values based on their internal binary  * representation  *  * @param a array containing integers to be sorted  * @param maxNumber the largest possible value if the array  */  public static void binaryRadixSort(Integer[] a, int maxNumber) { //TODO Project 3   int indexBucket0 = 0; int indexBucket1 = 0; final int NUMBER_OF_BUCKETS = 2; Integer[][] buckets = new Integer[NUMBER_OF_BUCKETS][a.length]; // // need to utilize bit related constants and methods from Integer class // } }// end SortArray

import java.util.Arrays; import java.util.Random;  public class CheckQuickSort { public static void main(String args[]) { int[] arraySizes = {1, 2, 3, 4, 5, 6, 7, 8, 9, 39, 40, 41, 50, 72, 100}; final int MAX_NUMBER = 99; Integer data[]; Integer forTesting[]; for (int i = 0; i < arraySizes.length; i++) { System.out.println(" ===> TEST array of size " + arraySizes[i]); Random generator = new Random(11); // create an array and fill it with random values between 0 and MAX_NUMBER data = new Integer[arraySizes[i]]; for (int j = 0; j < data.length; j++) { data[j] = generator.nextInt(MAX_NUMBER + 1); } System.out.println("The original array is: "); System.out.println(Arrays.toString(data)); // make a copy of the original array we will sort it and use it for comparing result forTesting = Arrays.copyOf(data, data.length); Arrays.sort(forTesting); SortArray.quickSort(data, data.length); System.out.println("The original array sorted with quickSort: "); System.out.println(Arrays.toString(data)); System.out.println(Arrays.equals(data, forTesting) ? " passes" : " fails"); } } }

See the sample run from CheckQuickSort.java driver:

===> TEST array of size 1

The original array is:

[38]