ICS 211 Homework H02: Sorting Arrays

Create an ArraySorter class that can sort Arrays.

Purpose

When we are dealing with data, we often want to put it in ‘order’. To do this we can sort it. In this assignment you will implement three simple sorts and analyze the sorting algorithms and your code.

In this assignment we have some specific requirements for your code. We have to satisfy the requirements of the problem in order to have correct solutions. This will give you early practice of writing code that meets some simple requirements.

Tasks

1. Create a package named edu.ics211.h02

This is where we will put all our classes for homework 02.

2. Create a generic class named ArraySorter that implements the SortableArray interface

public interface SortableArray<E> {
  void insertionSort(E[] data, Comparator<E> compare);
  void bubbleSort(E[] data, Comparator<E> compare);
  void selectionSort(E[] data, Comparator<E> compare);
  int getNumberOfSwaps();
  int getNumberOfComparisons();
  double getSortTime();
}

Each method should implement the named simple sort algorithm on the array data. Use the Comparator<E> to determine the order of the items in the array. Sort the arrays in ascending order. The ‘smallest’ element should be in position 0, ‘largest’ in data.length - 1.

The methods should keep track of the number of comparisons, number of swaps and the amount of time it took to sort the array. To record the time taken, your code should call System.nanoTime at the beginning of each of the methods and save the value as the start time. It should then call System.nanoTime again at the end, and print the difference between the two times. The difference may be zero if your system clock does not update the time quickly enough, but otherwise should accurately report how many nanoseconds (billionths of a second) it took to execute your code. When the sort methods complete they should report the number of comparison, swaps, and the execution time in nanoseconds.

Requirements

• Ensure that your implementation has the following characteristics:

  • The BigO for insertion and bubble sort on sorted data must be BigO(n);

  • The number of swaps for all three sorts on sorted data must be 0.

3. Create some Comparators in package edu.ics211.h01

• Create an IbuComparator that implements Comparator<Beer> deciding based upon the beers’ ibu values.

• Create an AbvComparator that implements Comparator<Beer> deciding based upon the beers’ abv values.

If you created them last week you are done. If not create them in package edu.ics211.h01.

Testing

We are going to use the FlightSorter.java JUnit tests to evaluate your homework for correctness.

You may add any more tests if you want to.

Algorithm Analysis

Write up a runtime analysis of each of the sorting methods, giving the big-O of each, and explaining how you got your results. Send your analysis to the TA together with your code. This part counts for 25% of the grade on this assignment. Even if your code doesn’t work, you should do this part to the best of your ability.

Grading Rubric