Question
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 staticmergeSort(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]
The original array sorted with quickSort:
[38]
passes
===> TEST array of size 2
The original array is:
[38, 68]
The original array sorted with quickSort:
[38, 68]
passes
===> TEST array of size 3
The original array is:
[38, 68, 11]
The original array sorted with quickSort:
[11, 38, 68]
passes
===> TEST array of size 4
The original array is:
[38, 68, 11, 55]
The original array sorted with quickSort:
[11, 38, 55, 68]
passes
===> TEST array of size 5
The original array is:
[38, 68, 11, 55, 33]
The original array sorted with quickSort:
[11, 33, 38, 55, 68]
passes
===> TEST array of size 6
The original array is:
[38, 68, 11, 55, 33, 7]
The original array sorted with quickSort:
[7, 11, 33, 38, 55, 68]
passes
===> TEST array of size 7
The original array is:
[38, 68, 11, 55, 33, 7, 40]
The original array sorted with quickSort:
[7, 11, 33, 38, 40, 55, 68]
passes
===> TEST array of size 8
The original array is:
[38, 68, 11, 55, 33, 7, 40, 33]
The original array sorted with quickSort:
[7, 11, 33, 33, 38, 40, 55, 68]
passes
===> TEST array of size 9
The original array is:
[38, 68, 11, 55, 33, 7, 40, 33, 93]
The original array sorted with quickSort:
[7, 11, 33, 33, 38, 40, 55, 68, 93]
passes
===> TEST array of size 39
The original array is:
[38, 68, 11, 55, 33, 7, 40, 33, 93, 7, 14, 94, 87, 9, 62, 18, 94, 91, 28, 6, 25, 5, 81, 8, 57, 48, 21, 94, 54, 29, 8, 11, 36, 15, 79, 68, 74, 29, 92]
The original array sorted with quickSort:
[5, 6, 7, 7, 8, 8, 9, 11, 11, 14, 15, 18, 21, 25, 28, 29, 29, 33, 33, 36, 38, 40, 48, 54, 55, 57, 62, 68, 68, 74, 79, 81, 87, 91, 92, 93, 94, 94, 94]
passes
===> TEST array of size 40
The original array is:
[38, 68, 11, 55, 33, 7, 40, 33, 93, 7, 14, 94, 87, 9, 62, 18, 94, 91, 28, 6, 25, 5, 81, 8, 57, 48, 21, 94, 54, 29, 8, 11, 36, 15, 79, 68, 74, 29, 92, 32]
The original array sorted with quickSort:
[5, 6, 7, 7, 8, 8, 9, 11, 11, 14, 15, 18, 21, 25, 28, 29, 29, 32, 33, 33, 36, 38, 40, 48, 54, 55, 57, 62, 68, 68, 74, 79, 81, 87, 91, 92, 93, 94, 94, 94]
passes
===> TEST array of size 41
The original array is:
[38, 68, 11, 55, 33, 7, 40, 33, 93, 7, 14, 94, 87, 9, 62, 18, 94, 91, 28, 6, 25, 5, 81, 8, 57, 48, 21, 94, 54, 29, 8, 11, 36, 15, 79, 68, 74, 29, 92, 32, 42]
The original array sorted with quickSort:
[5, 6, 7, 7, 8, 8, 9, 11, 11, 14, 15, 18, 21, 25, 28, 29, 29, 32, 33, 33, 36, 38, 40, 42, 48, 54, 55, 57, 62, 68, 68, 74, 79, 81, 87, 91, 92, 93, 94, 94, 94]
passes
===> TEST array of size 50
The original array is:
[38, 68, 11, 55, 33, 7, 40, 33, 93, 7, 14, 94, 87, 9, 62, 18, 94, 91, 28, 6, 25, 5, 81, 8, 57, 48, 21, 94, 54, 29, 8, 11, 36, 15, 79, 68, 74, 29, 92, 32, 42, 23, 14, 67, 96, 0, 44, 94, 29, 38]
The original array sorted with quickSort:
[0, 5, 6, 7, 7, 8, 8, 9, 11, 11, 14, 14, 15, 18, 21, 23, 25, 28, 29, 29, 29, 32, 33, 33, 36, 38, 38, 40, 42, 44, 48, 54, 55, 57, 62, 67, 68, 68, 74, 79, 81, 87, 91, 92, 93, 94, 94, 94, 94, 96]
passes
===> TEST array of size 67
The original array is:
[38, 68, 11, 55, 33, 7, 40, 33, 93, 7, 14, 94, 87, 9, 62, 18, 94, 91, 28, 6, 25, 5, 81, 8, 57, 48, 21, 94, 54, 29, 8, 11, 36, 15, 79, 68, 74, 29, 92, 32, 42, 23, 14, 67, 96, 0, 44, 94, 29, 38, 85, 16, 30, 4, 11, 19, 9, 36, 69, 5, 73, 77, 65, 72, 73, 74, 46]
The original array sorted with quickSort:
[0, 4, 5, 5, 6, 7, 7, 8, 8, 9, 9, 11, 11, 11, 14, 14, 15, 16, 18, 19, 21, 23, 25, 28, 29, 29, 29, 30, 32, 33, 33, 36, 36, 38, 38, 40, 42, 44, 46, 48, 54, 55, 57, 62, 65, 67, 68, 68, 69, 72, 73, 73, 74, 74, 77, 79, 81, 85, 87, 91, 92, 93, 94, 94, 94, 94, 96]
passes
===> TEST array of size 72
The original array is:
[38, 68, 11, 55, 33, 7, 40, 33, 93, 7, 14, 94, 87, 9, 62, 18, 94, 91, 28, 6, 25, 5, 81, 8, 57, 48, 21, 94, 54, 29, 8, 11, 36, 15, 79, 68, 74, 29, 92, 32, 42, 23, 14, 67, 96, 0, 44, 94, 29, 38, 85, 16, 30, 4, 11, 19, 9, 36, 69, 5, 73, 77, 65, 72, 73, 74, 46, 41, 7, 37, 43, 72]
The original array sorted with quickSort:
[0, 4, 5, 5, 6, 7, 7, 7, 8, 8, 9, 9, 11, 11, 11, 14, 14, 15, 16, 18, 19, 21, 23, 25, 28, 29, 29, 29, 30, 32, 33, 33, 36, 36, 37, 38, 38, 40, 41, 42, 43, 44, 46, 48, 54, 55, 57, 62, 65, 67, 68, 68, 69, 72, 72, 73, 73, 74, 74, 77, 79, 81, 85, 87, 91, 92, 93, 94, 94, 94, 94, 96]
passes
===> TEST array of size 100
The original array is:
[38, 68, 11, 55, 33, 7, 40, 33, 93, 7, 14, 94, 87, 9, 62, 18, 94, 91, 28, 6, 25, 5, 81, 8, 57, 48, 21, 94, 54, 29, 8, 11, 36, 15, 79, 68, 74, 29, 92, 32, 42, 23, 14, 67, 96, 0, 44, 94, 29, 38, 85, 16, 30, 4, 11, 19, 9, 36, 69, 5, 73, 77, 65, 72, 73, 74, 46, 41, 7, 37, 43, 72, 79, 92, 47, 18, 58, 50, 94, 1, 54, 4, 81, 41, 67, 78, 69, 12, 5, 76, 32, 55, 13, 66, 73, 41, 66, 27, 63, 66]
The original array sorted with quickSort:
[0, 1, 4, 4, 5, 5, 5, 6, 7, 7, 7, 8, 8, 9, 9, 11, 11, 11, 12, 13, 14, 14, 15, 16, 18, 18, 19, 21, 23, 25, 27, 28, 29, 29, 29, 30, 32, 32, 33, 33, 36, 36, 37, 38, 38, 40, 41, 41, 41, 42, 43, 44, 46, 47, 48, 50, 54, 54, 55, 55, 57, 58, 62, 63, 65, 66, 66, 66, 67, 67, 68, 68, 69, 69, 72, 72, 73, 73, 73, 74, 74, 76, 77, 78, 79, 79, 81, 81, 85, 87, 91, 92, 92, 93, 94, 94, 94, 94, 94, 96]
passes
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started