Sorting


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.

Selection Sort

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];

Bubble Sort

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.

Insertion Sort

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.


All the above sorting algorithms run in quadratic time, or 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.

Merge Sort

This recursive algorithm belongs to the very important divide-and-conquer paradigm. It consists of the following steps:

  1. 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.)

  2. Conquer - Sort each of these smaller groups of elements (by recursive calls).

  3. 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

Heap Sort

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

Your Task

  1. Create a directory and download the following files:

  2. Implement heapsort() and buildheap().

  3. 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.


    BU CAS CS - Sorting
    This page created by Jonathan Alon <jalon@cs.bu.edu>.
    Some material adapted from the textbook "Data Structures and Other Objects Using C++", by Main and Savitch. Mergesort example taken from the textbook "Introduction to Algorithms", by Cormen, Leiserson and Rivest.