COMP2711/8801
Computer Programming 2
Flinders University
Assignment: Median Wars
For the purposes of this assignment, the median of a collection of values is the one that is ‘in the middle’ of the collec-
tion. If you arranged the values in increasing order, the median would be the one whose position is midway along the
list. If the size of the list is even, use the value on the high side of the mid point (the upper median).
Medians are often found using selection algorithms; the median of n items can be found by selecting for item n/2. In
this assignment, you will explore median finding algorithms based on the quickselect and counting select procedures.
Background
Quickselect uses the same partitioning idea as quicksort. After a partition, the item chosen as the pivot will have all
smaller items to its left and all larger items to its right, which means it will be in its correct position in the list. If the
position of the pivot is not the one you are looking for, the algorithm proceeds by selecting in either the left or right
sublists, depending on which side of the pivot position the desired item falls.
// Return the kth smallest item
int quickSelect(int items[], int first, int last, int k)
{
int pivot = partition(items, first, last);
if (pivot > first + k) {
return quickSelect(items, first, pivot, k);
}
else if (pivot < first + k) {
return quickSelect(items, pivot+1, last, first + k - pivot);
}
else {
return items[pivot];
}
}
Counting select uses a similar approach to counting sort, whereby items in the list are used as indexes into an array of
counts. Initially the count array contains all zeros. As the list is traversed, the appropriate count values are incremented;
when all items have been processed, the value at each index is a count of the number of times an item equal to the index
was present in the list. Once the counts have been determined, the kth item can be found by beginning at the low value
end of the array and accumulating counts until the total exceeds k.
// Return the kth smallest item (assumes 0 <= item value < MAX_ITEM)
int countingSelect(int items[], int first, int last, int k)
{
int counts[MAX_ITEM];
for (int c = 0; c < MAX_ITEM; c++) {
counts[c] = 0;
}
for (int i = first; i < last; i++) {
counts[items[i]] += 1;
}
int c = 0;
while (k >= 0) {
k -= counts[c++];
}
return c-1;
}
Question 1 (10 marks)
Explain the median finding algorithms based on quickselect and counting select in a way that would be understandable
to an intelligent lay person. You should not use any code (or even pseudo code) in your explanation, but you may need
to use general concepts such as compare, swap, and copy, and you will certainly need to use procedural words such as if
and repeat.
Flinders University / College of Science and Engineering 1
COMP2711/8801
Computer Programming 2
Flinders University
You might find it helpful to consider an algorithm as if it were a game for which you need to define the rules. For ex-
ample, an easy-to-understand select algorithm (though not a very efficient one) is based on a truncated version of selec-
tion sort, where the sort is stopped when the kth smallest item is moved into position:
// Return the kth smallest item
int selectionSelect(int items[], int first, int last, int k)

{
for (int i = first; i <= first + k; i++) {
int min = i;
for (int j = i + 1; j < last; j++) {
if (items[j] < items[min]) {
min = j;

}
}
swap(items[i], items[min]);
}
return items[k];
}
If your task was to describe how you could use this approach to find the median, you could describe the process as if it
was a game of solitaire played with a deck of cards that contains the values to process. For example:
Question 2 (10 marks)
Write a set of guidelines for deciding which of the two median finding algorithms would be most appropriate for a par-
ticular situation. Include in your guidelines a description of the advantages and disadvantages of each algorithm, togeth-
er with an indication as to why those characteristics apply. Your goal should be to provide enough information so that
someone unfamiliar with the details of each algorithm would be able to decide which one is right for them.
Learning outcomes
• Understand and appropriately use the language and terminology of data abstraction and object-oriented programming;
• Describe common data structures and choose appropriate data structures for specific application needs;
• Understand and appropriate use the language and terminology of algorithm analysis;
• Determine the time and space complexity of simple algorithms;
• Describe the advantages and disadvantages of different algorithmic approaches in specific application contexts.
Submission
This assignment is to be completed individually. Your submission should conform to accepted practises for academic
writing, use a consistent typeface, and be free of grammatical and spelling errors. British English is the preferred docu-
ment language. Of course, you must give appropriate acknowledgement to any material that you use or reference—use
either Harvard or IEEE format for citations.
Submit your work as a single PDF to the Assignment submission box on FLO by 11.55pm Monday 1 June (week 12).
This assignment is worth 20% of the overall topic grade.
Flinders University / College of Science and Engineering 2
Median in the middle
The playing area consists of four 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 to
begin the tableau, then turn over the the next card. If the stock card is smaller than the tableau card, play it
on the tableau; otherwise, discard it. When all of the cards in the stock have been played, move the topmost
tableau card to the foundation. Then combine the remaining tableau cards with the discards to form the
stock for the next round.
Continue to play rounds until the number of cards in the foundation is greater than the number of cards in
the stock. The median card is then the topmost card in the foundation.