# Sort Bakeoff

## Disclaimer

This essay does not describe an existing computer program, just one that should exist. This essay is about a suggested student project in Java programming. This essay gives a rough overview of how it might work. I have no source, object, specifications, file layouts or anything else useful to implementing this project. Everything I have prepared to help you is right here.

This project outline is not like the artificial, tidy little problems you are spoon-fed in school, when all the facts you need are included, nothing extraneous is mentioned, the answer is fully specified, along with hints to nudge you toward a single expected canonical solution. This project is much more like the real world of messy problems where it is up to you to fully the define the end point, or a series of ever more difficult versions of this project and research the information yourself to solve them.

Everything I have to say to help you with this project is written below. I am not prepared to help you implement it; or give you any additional materials. I have too many other projects of my own.

Though I am a programmer by profession, I don’t do people’s homework for them. That just robs them of an education.

You have my full permission to implement this project in any way you please and to keep all the profits from your endeavour.

The intent of this exercise is to compare various sorting algorithms under various conditions:

• small sorts
• large sorts
• simple keys
• complex keys where a comparison is a fairly expensive operation

The algorithms you might use include:

• Sun Sort
• QuickSort
• HeapSort
• ShellSort
• TreeSort where you sort by putting all elements in a TreeSet
• PileSort where you pick N random elements from your set and put them into N piles (an ArrayList) then sort these pivot elements with an insertion sort in a little array. Then put the rest of the elements into the corresponding pile (an ArrayList) using a binary search on the array to select the correct pile. Then recursively sort each pile the same way. Experiment to find the optimal size for N.
• Insertion sort: add elements one at a time sliding elements down in an array to make room for the new element. Use an array rather than an ArrayList for speed.
• Bubble Sort the world’s worst sort

This is a fairly easy project since most of the sorts are already written for you. You might use the state/county/city data in AmericanTax as your sample data for some real world complex keys.

background on sorting
Comparator Cutter: to generate Comparator and Comparable code
HeapSort
QuickSort