Sort Wars

COMP8801 Flinders University
Computer Programming 2 GE
Investigation: Sort Wars
If quicksort is so quick, why bother with anything else? If bubble sort is so bad, why even mention it? For that matter,
why are there so many different sorting algorithms? Your task is to investigate these and other questions in relation to the
algorithms selection sort, insertion sort, merge sort, and quicksort.
Task
1. Explain the selection sort, insertion sort (fast or slow), merge sort, and quicksort algorithms in such a way that an
intelligent lay person would be able to understand how they work. Whilst you may wish to consult the lecture notes
to re-familiarise yourself with the inner workings of each algorithm, your explanations
should not include any code
(or pseudo code). However, you will likely need to use general concepts such as
compare and swap, and you will
almost certainly need to use procedural words such as
if and repeat.
You may find it helpful to consider how you would explain the algorithms to your friend studying a non-IT degree.
One approach would be to treat each algorithm as if it were a game for which you need to define the rules. For
example, here is how you could describe the bubble sort algorithm as if it were a game of solitaire played with a deck
of cards that contain the values to process.
The playing area consists of several regions: foundation, tableau, stock, and discard. Initially, all cards are in the stock.
Play consists of a number of rounds. To begin a round, place the top card of the stock face up in the tableau then turn over the
next card. If the stock card is smaller that the tableau card, place it face down on the discard pile; otherwise, place the tableau card
on the discard pile and the stock card in the tableau. Play the remaining stock cards in the same way, then move the final tableau
card, which will be the largest of the stock cards, to the foundation and use the discard pile as the new stock. This completes one
round. Continue to play rounds until the stock is empty. The cards in the foundation will now be sorted with the smallest on top.
2. Write a set of guidelines for each algorithm to help someone decide which one would be most appropriate for a
particular situation. Include in your guidelines a description of the advantages and disadvantages, together with an
indication as to why those characteristics apply, and an explanation of the running cost (in Big-O notation). Your goal
is to provide enough information so that someone unfamiliar with the inner workings of each algorithm would be able
to decide which one is right for them.
For example, if someone was considering using counting sort to sort a collection of values then the following brief
information could help them decide if it was appropriate or not.

Algorithm Counting Sort
Description Count the number of times each different value appears, then overwrite the values in lowest-to-highest
order, with each value repeated according to the counts.
Advantages • Usually faster than any of the comparison-based sorts.
• Algorithmic complexity is O(n + k), irrespective of the data order, where
n is the list length and k is
the number of distinct values that might occur. Typical case is where
k is much less than n, in which
case the cost is O(n).
• Simple to code.
Disadvantages • Only usable where the values to be sorted can be used to index an array of value counts, which usually
means the values are integers over a small range. In other words, the algorithm cannot be used to sort
common non-integral values such as strings and floats, and it is inappropriate even for integers if the
range of values is large.
• Requires an auxiliary array (to store the counts) of size equal to the number of different possible sort
values. If the range of values is large, the cost of allocating and maintaining this array could be
significant.
When to use… If your circumstances allow, it is hard to beat this algorithm, but because it places very tight restrictions
on the nature of the data to sort, you will often have to choose another approach.

Flinders University / College of Science and Engineering 1 COMP8801 Flinders University
Computer Programming 2 GE
Submission
This assignment is to be completed individually.
Your submission should conform to accepted practices for academic writing, which means you should use a consistent
typeface, number your headings, and ensure your work is free of grammatical and spelling errors. British English is the
preferred document language. Any material you reference must be appropriately acknowledged with an in-text citation
and an accompanying full citation in a bibliography at the end of your document—use either Harvard or IEEE format.
Submit your work as a single PDF document to the
investigation submission box on FLO by 5PM Friday 10 June (week
13)
. The assignment will be graded out of 10 with each question contributing 5 marks.
Learning outcomes
As per the topic SAM, this assignment is designed to enable you to meet learning outcomes LO1–9.
Flinders University / College of Science and Engineering 2