Homework 3: sorting

You have been given the following code: HW3.java

import java.util.*;

public class HW3 { static Random rand = new Random(); static int numComparisons = 0;

// 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 pivot = partition(a, low, high); // Partition the array into two halves quicksort(a, low, pivot-1); // Sort the left half quicksort(a, pivot+1, high); // Sort the right half }

// ***Modify this method to choose a random pivot*** // Partitions the array and returns pivot such that a[low..pivot-1] <= a[pivot] <= a[pivot+1..high]. // This implementation uses Lomuto's partitioning scheme. private static int partition(int[] a, int low, int high) { int pivot = a[high]; // Choose the rightmost element in the range as the pivot int i = low; for (int j = low; j < high; ++j) { // Compare each element to the pivot if (a[j] < pivot) // If it's less than the pivot, move it to the left half by swapping swap(a, i++, j); //++numComparisons; } swap(a, i, high); // Swap the pivot with the leftmost element in the right half return i; }

// 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; }

// Sorts each row of the 2D array and measures the average runtime and number of comparisons. private static void runTest(int[][] arrays) { long start = System.currentTimeMillis(); for (int i = 0; i < NUM_ARRAYS; ++i) // Sort each array quicksort(arrays[i]); long end = System.currentTimeMillis(); System.out.println("Average runtime in seconds: " + (end-start) / 1000.0 / NUM_ARRAYS); if (numComparisons != 0) { // numComparisons will be 0 if ++numComparisons is commented-out System.out.println("Average number of comparisons: " + (double)numComparisons / NUM_ARRAYS); numComparisons = 0; // Reset counter } for (int i = 0; i < NUM_ARRAYS; ++i) { // Verify that all arrays are sorted if (!isSorted(arrays[i])) { System.out.println("The arrays are not sorted"); return; } } }

static final int ARRAY_SIZE = 100000, NUM_ARRAYS = 100; public static void main(String[] args) { // Create the arrays int[][] randomArray = new int[NUM_ARRAYS][ARRAY_SIZE]; int[][] sortedArray = new int[NUM_ARRAYS][ARRAY_SIZE]; int[][] allZero = new int[NUM_ARRAYS][ARRAY_SIZE]; // Fill the arrays with values for (int i = 0; i < NUM_ARRAYS; ++i) { for (int j = 0; j < ARRAY_SIZE; ++j) { randomArray[i][j] = rand.nextInt(); sortedArray[i][j] = j; allZero[i][j] = 0; } }

System.out.println("***Random arrays***"); runTest(randomArray);

System.out.println(" ***Already-sorted arrays***"); runTest(sortedArray);

System.out.println(" ***All-zero arrays***"); runTest(allZero); } }

RandomInts.java (this is not part of the homework, it's just an example of how to generate random integers) import java.util.*; public class RandomInts { static Random rand = new Random(); public static void main(String[] args) { int low = 3, high = 7; int random = rand.nextInt(high-low+1)+low; // Generates a random integer between low and high (inclusive) System.out.println(random); } }

The quicksort method in HW3.java is not very optimized. In this assignment, you will be making two improvements to the code. You will also be measuring runtimes and counting comparisons. You should submit two files:

HW3.java (code)

hw3.txt (runtimes, comparisons)

Sample hw3.txt file (replace the blank lines with your answers)

***Original code, before making changes***

Average runtime in seconds (random arrays): __________ Average runtime in seconds (already-sorted arrays): __________ Average runtime in seconds (all-zero arrays): __________

(++numComparisons should be uncommented at this point)

Average number of comparisons (random arrays): __________ n = 100000 nlogn = __________ Compared to nlogn, the number of comparisons is __________ (much more? slightly more? slightly less?)

(++numComparisons should be commented-out at this point)

***Modify quicksort to use insertion sort for small subarrays***

Threshold = 8 Average runtime in seconds (random arrays): __________

Threshold = 32 Average runtime in seconds (random arrays): __________

Threshold = 64 Average runtime in seconds (random arrays): __________

Threshold = 512 Average runtime in seconds (random arrays): __________

The best threshold(s) seems to be __________

(the threshold should be set to what you think is the best choice)

***Modify partition to choose a random pivot***

Average runtime in seconds (random arrays): __________ Average runtime in seconds (already-sorted arrays): __________ Average runtime in seconds (all-zero arrays): __________

This homework is worth only 70 points instead of 100 (40 points for the code, 30 points for hw3.txt).

Measuring runtime

Algorithms may perform well on some inputs and poorly on other inputs, so it is important to test algorithms on a variety of inputs. We will test quicksort on random arrays, already-sorted arrays, and all-zero arrays, each with 100,000 elements. To improve accuracy, we will take the average of 100 tests.

Before you make any changes to the code, run the program to measure the runtime for each type of input. Record the 3 runtimes in HW3.txt. If the stack overflows, don't worry about it. Check which test(s) caused it to overflow and write "slow" as the result, then comment out the test so you can do the other tests.

In the partition method, uncomment ++numComparisons. Now the program will count the number of comparisons. Run the program again and record the number of comparisons for sorting a random array in HW3.txt. Record the value of nlog₂n (use a calculator). Which number is larger? Is it just a little larger, or much larger?

Comment-out ++numComparisons before you start the next part of the homework (to avoid slowing down the runtime).

Insertion sort for small subarrays

Although insertion sort is O(n²) 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 the portion of the array currently being sorted). If the size is smaller than the threshold, sort it with insertion sort instead of quicksort (you have been given an insertionsort method). Test 4 different thresholds: 8, 32, 64, 512.

For each threshold, record the runtime for sorting a random array. Which threshold do you think is the best choice? If you think multiple thresholds are equally good, then say so.

Set the threshold to what you think is the best choice before you start the next part of the homework.

Random pivot

If the pivot is chosen deterministically, certain inputs will always have the worst-case runtime, because every element will end up on the same side of the pivot. One way to fix this is to choose a random pivot.

Modify the partition method so that it uses a random pivot. At the beginning of the method, choose a random element in the range a[low..high] to swap with a[high], before choosing a[high] as the pivot (because in Lomuto partitioning, the pivot must be the rightmost element).

Measure the runtime again for all 3 types of input. If your code is correct, one of the previously "slow" runtimes should be faster. One of the tests still cause the stack to overflow, so write "slow" as the result (to fix it you'd have to use a different partitioning scheme, but this is not required for the homework).

Duplicate elements

You do not have to do anything here. It's only for your information. Some partitioning schemes perform poorly when there are many duplicate elements. When implementing an algorithm, it is important to consider all possible situations. Quicksort with Hoare partitioning is O(nlogn) in the case where all elements are equal. Another option is to use Dijkstra's 3-way partitioning, which is O(n) in the case where all elements are equal. This method partitions the array into 3 sections, which are less than, equal to, and greater than the pivot.