Modified Quick Sort

You have been given the following code:

import java.util.*;

public class HW3 {

// Swaps the elements at indices i and j.
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}

// Sorts the elements in the range a[low..high].
private static void insertionsort(int[] a, int low, int high) {
for (int i = low+1; i <= high; ++i) {
int temp = a[i], j = i-1; // Save the current element
while (j >= low && a[j] > temp) { // Shift all elements greater than it to the right
a[j+1] = a[j];
--j;
}
a[j+1] = temp; // Insert the current element into the correct spot
}
}

public static void quicksort(int[] a) {
quicksort(a, 0, a.length-1);
}

// ***Modify this method to use insertion sort for small subarrays***
// Sorts the elements in the range a[low..high].
private static void quicksort(int[] a, int low, int high) {
if (low >= high) return;
int pivotIndex = partition(a, low, high); // Partition the array into two halves
quicksort(a, low, pivotIndex); // Sort the left half
quicksort(a, pivotIndex+1, high); // Sort the right half
}

// Partitions the array and returns the pivot index such that a[low..pivotIndex] <= pivotValue <= a[pivotIndex+1..high].
// Note that pivotValue will not necessarily be at a[pivotIndex].
// This implementation uses Hoare's partitioning scheme.
private static int partition(int[] a, int low, int high) {
int pivotValue = a[low]; // Choose the leftmost element in the range as the pivot
int i = low-1, j = high+1;
while(true) {
do {i++;} while(a[i] < pivotValue); // Find an element >= pivot
do {j--;} while(a[j] > pivotValue); // Find an element <= pivot
if (i < j) swap(a, i, j); // If they're in the wrong order, swap them
else return j;
}
}

static Random rand = new Random();

// Returns true if the array is sorted. Otherwise returns false.
private static boolean isSorted(int[] a) {
for (int i = 0; i < a.length-1; ++i)
if (a[i] > a[i+1])
return false;
return true;
}

// Generates numArrays random arrays, each with arraySize elements,
// then sorts the arrays and prints the average runtime.
private static void runTest(int numArrays, int arraySize) {
int[][] randomArrays = new int[numArrays][arraySize];

// Fill the arrays with values
for (int i = 0; i < numArrays; ++i) {
for (int j = 0; j < arraySize; ++j) {
randomArrays[i][j] = rand.nextInt();
}
}

long start = System.currentTimeMillis();
for (int i = 0; i < numArrays; ++i) // Sort each array
quicksort(randomArrays[i]);
long end = System.currentTimeMillis();

System.out.println("Average runtime in seconds: " + (end-start) / 1000.0 / numArrays);

for (int i = 0; i < numArrays; ++i) { // Verify that all arrays are sorted
if (!isSorted(randomArrays[i])) {
System.out.println("The arrays are not sorted");
return;
}
}
}

public static void main(String[] args) {
int numArrays = 100, arraySize = 100000;
runTest(numArrays, arraySize);
}
}

The quicksort method in HW3.java is not very optimized. In this assignment, you will make an improvements to the code, and measure runtimes before and after making the improvement. You should submit two files:

• HW3.java (code)
• hw3.txt (runtimes)

Measuring runtime

Quicksort runs faster on some inputs, and slower on other inputs. Therefore it is important to run many tests to ensure that the result was not lucky. You have been given a runTest which generates many random arrays, sorts each array, and prints the average runtime.

• Before you modify the code, run the program to measure the average runtime to sort 100 random arrays, each with 100000 elements. Record the runtimes in HW3.txt.

Insertion sort for small subarrays

Although insertion sort is O(n2) and quicksort is O(nlogn), insertion sort is faster for small arrays.

• Modify quicksort so that each time you call quicksort recursively, check the size of the subarray (the "subarray" is the portion of the array currently being sorted, from index low to index high). If the size is smaller than the threshold, sort it with insertion sort instead of quicksort (you have been given an insertionsort method). Run the program 4 times with 4 different thresholds: 8, 32, 64, 1024.
• For each threshold, record the average runtime. Which threshold gives the best runtime?