Sorting

We will walk through selection sort, insertion sort, mergesort, and quicksort to discuss:

  • How it works (accompanied by a hand trace)
  • What it’s best/worst/average cases are
  • How to count its complexity

I will use this animation to practice with you

In this unit you’re going to have a lot less lead off about where we’re headed, more like a Computing Scientist would actually have to do when given a problem. So here’s your problem:

Part I

You will be entering a competition in which you will have to provide 2 O(n^2) and 2 O(nlgn) sorting algorithms (average case). Your algorithms will be pitted against the algorithms of your classmates to see who’s code is able to successfully sort an array of Compareable objects fastest. There will also be a wildcard round, one where you can enter any algorithm of your choice (perhaps a hybrid or your very own new method). In the wildcard round you can be assured that the type of data will be an Integer. This opens the door for you to explore non-comparison based sorting algorithms if you wish. Altogether you will have 5 sorting algorithms to submit.

This list at Wikipedia is a good starting point.

Here is the interface that you will need to implement in order to participate in the competition.

There are also plenty of places with demonstrations of how the algorithms run

Deliverables: Part I

  • Source code
  • Hand trace of the algorithms with 8 integers showing how it works

Part II

You’ve already come across the notation but we will look more at complexity here to see how we analyze algorithms in CS.

Here are the examples we’ll discuss together

The first thing we’re going to do is get some data. Instead of simply sorting the array you are given, you will now return the number of comparisons you are making in order to complete the algorithm.

  • public void sort -> public int sort

Now we will write a driver program that will take in:

  • a value for the size of the array to sort
  • the number of times to repeat the sorting

It will produce the average number of comparisons for that trial run:

How many items would you like to sort? 10

How many test runs do you want to perform? 1000

The average comparisons were:

  • Selection Sort: 70
  • Insertion Sort: 88
  • Mergesort: 62
  • …

Now modify your driver program to run multiple trials of different array sizes and send it out to a CSV:

Size,10,100,1000,…

Insertion Sort,70,10052,1233452,…

Selection Sort,88,9253,89754,…

Mergesort,62,1023,12543,…

Finally, you can use Excel to open the file and add a graph of the data to show the run time behaviour.

Deliverables: Part II

  • Driver program code
  • Printed excel code showing data/graph
  • Analysis of any two sorting algorithms by hand, explaining how to arrive at the correct complexity.