One common programming task is sorting a list of values. For example, we may want to view a list of student records sorted by student ID or alphabetically by student name. We may want to sort the list from the lowest value (of the student ID or name) to the highest (ascending order), or from highest to lowest (descending order).
Here, we will briefly review a few different sorting algorithms and
their performance. We will assume without loss of generality that the
different algorithms sort an array in ascending order, and we shall
call this array data
. We will also assume the availability
of a standard swap
routine.
In this algorithm, we rearrange the the values of the array so that
data[0]
is the smallest, data[1]
is the next
smallest, and so forth up to data[n-1]
, the largest.
Pseudo-code for this algorithm would be:
for(i=0; i<n; i++) Put the next smallest element in location data[i];
This algorithm looks at pairs of entries in the array, and swaps their order if needed. After the first step of the algorithm the maximal value will "bubble" up the list and will occupy the last entry. After the second iteration, the second largest value will "bubble" up the list and will occupy the next to last entry, and so on. For example, if our initial array is:
(8, 2, 5, 3, 10, 7, 1, 4, 6, 9)
Then, after the first step it will be:
(2, 5, 3, 8, 7, 1, 4, 6, 9, 10)
After the second step:
(2, 3, 5, 7, 1, 4, 6, 8, 9, 10)
And, after the third:
(2, 3, 5, 1, 4, 6, 7, 8, 9, 10)
Pseudo-code for this algorithm would be:
for (i=n-1; i>=0; i--) for (j=0; j<i; j++) if (data[j] > data[j+1]) swap(data[j], data[j+1])
Note that this algorithm can be improved if we keep track of whether a swap took place during an outer loop iteration. If there were no swaps, the algorithm may stop because the array is sorted.
This algorithm takes one value at a time and builds up another sorted list of values. It helps if you can imagine what you do when you play a game of cards: you pick a card and insert it to an already sorted list of cards. For example, if our initial array is:
(8, 2, 5, 3, 10, 7, 1, 4, 6, 9)
Then, after the first step it will be unchanged:
(8, 2, 5, 3, 10, 7, 1, 4, 6, 9)
After the second step:
(2, 8, 5, 3, 10, 7, 1, 4, 6, 9)
After the third:
(2, 5, 8, 3, 10, 7, 1, 4, 6, 9)
And so on until the entire array is sorted. Notice that the first part of the list, which is colored with red is always sorted.
Pseudo-code for this algorithm would be:
for(i=1; i<n; i++) ordered_insert(data, i, data[i]);
where ordered_insert()
inserts a new value in a sorted array,
so that the resulting array will also be sorted.
O(n^2)
. We will not give a rigorous proof, but rather give
the intuition why this is so. The reason is that in all of the above
algorithms an O(n)
process is performed n times.
Another explanation, which is closer to the rigorous proof, is to
realize that if you count the operations (and sum them up) in each of
the above algorithms then you get the formula:
1 + 2 + 3 + ... + n = n*(n+1) / 2 = n^2/2 + n/2 = O(n^2).
The following algorithms are more efficient, and by careful analysis
can be shown to run in time O(nlogn)
. For the following
algorithms, the design and analysis are much simplified, if we consider
array sizes which are powers of 2.
This recursive algorithm belongs to the very important divide-and-conquer paradigm. It consists of the following steps:
Divide the elements to be sorted into two groups of equal (or almost equal) size. (This is why it is easier if we assume that the array size is a power of 2.)
Conquer - Sort each of these smaller groups of elements (by recursive calls).
Merge - Combine the two sorted groups into one large sorted list.
For example:
sorted list ----------------------------- |1 2 2 3 4 5 6 6| ----------------------------- merge ------------- ------------- |2 4 5 6| |1 2 3 6| ------------- ------------- merge merge ----- ----- ----- ----- |2 5| |4 6| |1 3| |2 6| ----- ----- ----- ----- merge merge merge merge - - - - - - - - |5| |2| |4| |6| |1| |3| |2| |6| - - - - - - - - initial list
This algorithm starts by building a heap from the initial
array. Since the maximum element of the array is stored at the root,
data[0]
, it can be put into its correct final position by
exchanging it with data[n-1]
.
If we then "discard" node n-1 from the heap, we observe that
data[0..(n-2)]
can easily be made into a heap. The
children of the root remain heaps, but the new root element may violate
the heap property. All that is needed to restore the heap property,
however, is one call to reheapify_down()
, which leaves a
heap in data[0..(n-2)]
.
The heapsort algorithm then repeats this process for the heap of size n-2 down to a heap of size 1.
heapsort(vector<Item>& v) build_heap(v); // create a heap vector corresponding to v for(i=v.size()-1; i>=1; i--) swap(heap[0], heap[i]); heap-size = heap-size - 1; reheapify_down(); buildheap(vector<Item>& v) for(i=0; i<v.size(); i++) insert(v[i]);
A more efficient buildheap()
procedure will require a
slight modification to the reheapify_down()
routine to
take as an argument the index i of a node. So we would call
reheapify_down(i)
to reheapify down from node i, and
reheapify_down(0)
to reheapify down from the root.
buildheap(vector<Item> &v) heap-size = v.size(); for(i=v.size()/2 - 1; i >= 0; i--) reheapify_down(i); // reheapify from node i
Create a directory and download the following files:
Implement heapsort()
and buildheap()
.
Change the main program main.cpp
so that it reads the
input file into a vector and then calls heapsort()
with this
vector as an argument. Print this vector to verify that it indeed gets
sorted.
Note: In the proposed implementation, we assume two vectors.
The input vector and the heap vector. The heap vector is used to sort
the original vector v
. In your final implementation, you
may want to use only one vector (or array). It is possible! However, it
may require some more changes.