12.4. Sorting

Note

Common sorting algorithms are included in this section but, for the purpose of this course, only the essential ideas will be discussed and demonstrated.

Note

namespace

Note that to use the example files downloaded from GitHub, you need to keep the namespace consistent. It is recommended to use IntroCSCS (or IntroCS) and you have to check every file to make sure they are consistent. Failing to do so will incur an error “error CS0103: The name ‘CLASS’ does not exist in the current context”.

Sorting algorithms represent foundational knowledge that every computer scientist and IT professional should at least know at a basic level. It also turns out to be a great way of learning about why arrays are important.

In this section, we’re going to take a look at a number of well-known sorting algorithms with the hope of sensitizing you to the notion of performance–a topic that is covered in greater detail in courses such as algorithms and data structures.

This is not intended to be a comprehensive reference at all. The idea is to learn how these classic algorithms are coded in the teaching language for this course, C#, and to understand the essentials of analyzing their performance, both theoretically and experimentally. [1]

The sorts and supporting functions are all in sorting/sorting.cs, but we start one bit at a time:

12.4.1. Exchanging Array Elements

We’ll begin by introducing you to a simple method, whose only purpose in life is to swap two data values at positions m and n in a given integer array:

/// Exchange the elements of data at indices m and n.
public static void Exchange(int[] data, int m, int n)
{
   int temporary = data[m];
   data [m] = data[n];
   data [n] = temporary;
}

For example if we have an array nums, shown with indices:

 nums: -1  8 11 22  9 -5  2
index:  0  1  2  3  4  5  6

Then after Exchange(nums, 2, 5) the array would look like

 nums: -1  8 -5 22  9 11  2
index:  0  1  2  3  4  5  6

In general, swapping two values in an array is no different than swapping any two integers. Suppose we have the following integers a and b:

int a, b;
int t;

a = 25;
b = 35;
t = a;
a = b;
b = t;

After this code does its job, the value of a would be 35 and the value of b would be 25.

So in the Exchange() function above, if we have two different array elements at positions m and n, we are basically getting each value at these positions, e.g. data[m] and data[n] and treating them as if they were a and b in the above code.

You might find it helpful at this time to verify that the above code does what we’re saying it does, and a good way is to type it directly into the C# interpreter (csharp) so you can see it for yourself.

The Exchange() function is vital to all of the sorting algorithms in the following way. It is used whenever two items are found to be out of order. When this occurs, they will be swapped. This doesn’t mean that the item comes to its final resting place in the array. It just means that for the moment, the items have been reordered so we’ll get closer to having a sorted array.

Let’s now take a look at the various sorting algorithms.

12.4.2. Bubble Sort

The Bubble Sort algorithm works by repeatedly scanning through the array exchanging adjacent elements that are out of order. Watching this work with a strategically-placed Console.WriteLine() in the outer loop, you will see that the sorted array grows right to left. Each sweep picks up the largest remaining element and moves to the right as far as it can go. It is therefore not necessary to scan through the entire array each sweep, but only to the beginning of the sorted portion.

We define the number of inversions as the number of element pairs that are out of order. They needn’t be adjacent. If data[7] > data[16], that’s an inversion. Every time an inversion is required, we also say that there is corresponding data movement. If you look at the Exchange() code, you’ll observe that a swap requires three movements to take place, which happens very quickly on most processors but still amounts to a significant cost.

There can be at most \(N \cdot \frac{N-1}{2}\) inversions in the array of length \(N\). The maximum number of inversions occurs when the array is sorted in reverse order and has no equal elements.

Bubble Sort exchanges only adjacent elements. Each such exchange removes precisely one inversion; therefore, Bubble Sort requires \(O(N^2)\) exchanges.

public static void IntArrayBubbleSort (int[] data)
{
   int N = data.Length;
   for (int j=N-1; j>0; j--) {
      for (int i=0; i<j; i++) {
         if (data[i] > data[i + 1]) {
            Exchange (data, i, i + 1);
         }
      }
   }
}

12.4.3. Selection Sort

The Selection Sort algorithm works to minimize the amount of data movement, hence the number of Exchange() calls.

/// Among the indices >= start for data,
/// return the index of the minimal element.
public static int IntArrayMin (int[] data, int start)
{
   int N = data.Length, minPos = start;
   for (int pos=start+1; pos < N; pos++)
      if (data[pos] < data[minPos]) {
         minPos = pos;
      }
   return minPos;
}

public static void IntArraySelectionSort (int[] data)
{
   int N = data.Length;
   for (int i=0; i < N-1; i++) {
      int k = IntArrayMin(data, i);
      if (i != k) {
         Exchange(data, i, k);
      }
   }
}

It’s a remarkably simple algorithm to explain. As shown in the code, the actual sorting is done by a function, IntArraySelectionSort(), which takes an array of data as its only parameter, like Bubble sort. The way Selection Sort works is as follows:

1. An outer loop visits each item in the array to find out whether it is the minimum of all the elements after it. If it is not the minimum, it is going to be swapped with whatever item in the rest of the array is the minimum.

2. We use a helper function, IntArrayMin() to find the position of the minimum value in the rest of the array. This function has a parameter, start to indicate where we wish to begin the search. So as you can see from the loop in IntArraySelectionSort(), when we start with position i, and we compare to the later elements from position i + 1 to the end of the array, updating the position of the smallest element so far.

An illustration to accompany the discussion:

 data: 12  8 -5 22  9  2
index:  0  1  2  3  4  5
        i     k

The first time through the loop, i is 0, and k gets the value 2, since data[2] is -5, the smallest element. Those two positions get swapped.

 data: -5  8 12 22  9  2
index:  0  1  2  3  4  5

The next time through the loop i is 1 and k becomes 5:

 data: -5  8 12 22  9  2
index:  0  1  2  3  4  5
           i           k

After the swap:

 data: -5  2 12 22  9  8
index:  0  1  2  3  4  5

and so on. Here is the data after each of the last three swaps:

-5  2  8 22  9 12

-5  2  8  9 22 12

-5  2  8  9 12 22

Consider the first call to IntArrayMin.

 data: 12  8 -5 22  9  2
index:  0  1  2  3  4  5

Initially minPos is 0. Here are the changes for each value of pos:

pos=1:  8 = data[1] < data[0] = 12, so minPos becomes 1
pos=2: -5 = data[2] < data[1] = 8, so minPos becomes 2
pos=3: 22 = data[3] is not < data[2] = -5, so minPos still 2
pos=4:  9 = data[4] is not < data[2] = -5, so minPos still 2
pos=5:  2 = data[5] is not < data[2] = -5, so minPos still 2

and 2 gets returned, and we ge the swap

 data: -5  8 12 22  9  2
index:  0  1  2  3  4  5

The next call to IntArrayMin has start as 1, so minPos is initially 1, and we compare to the elements of data at index 2, 3, 4, and 5….

We won’t do the full algorithmic analysis here. Selection Sort is interesting because it does most of its work through comparisons, with the same number of them no matter how the data are ordered, exactly \(N \cdot \frac{N-1}{2}\), which is \(O(N^2)\) The number of exchanges is O(N). The comparisons are a non-trivial cost, however, and do show in our own performance experiments with randomly-generated data.

12.4.4. Insertion Sort

In the Insertion Sort algorithm, we build up a longer and longer sorted list from the bottom of the array. We repeatedly insert the next element into the sorted part of the array by sliding it down (using our familiar Exchange() method) to its proper position.

public static void IntArrayInsertionSort (int[] data)
{
   int N = data.Length;
   for (int j=1; j<N; j++) {
      for (int i=j; i>0 && data[i] < data[i-1]; i--) {
         Exchange (data, i, i - 1);
      }
   }
}

Consider the earlier example array as we illustrate some of the steps. I use the symbol ‘-’ for an element that we know to be in the sorted list at the beginning of the array, and ‘@’ over the next one we are trying to insert at the right position. We start with a one-element sorted list and try to position the second element:

        -  @
 data: 12  8 -5 22  9  2
index:  0  1  2  3  4  5

After each outer loop in sequence we end up with:

        -  -  @
 data:  8 12 -5 22  9  2
index:  0  1  2  3  4  5

        -  -  -  @
 data: -5  8 12 22  9  2
index:  0  1  2  3  4  5

        -  -  -  -  @
 data: -5  8 12 22  9  2
index:  0  1  2  3  4  5

        -  -  -  -  -  @
 data: -5  8  9 12 22  2
index:  0  1  2  3  4  5

        -  -  -  -  -  -
 data: -5  2  8  9 12 22
index:  0  1  2  3  4  5

Let us illustrate several times just through the inner loop, the first time, when the 8 is moved into position from index j = 1, so i starts at 1. We show the letter i over the data at index i, and show the comparison test to be done with a > with a ‘?’ over it.

          ? i
 data: 12 > 8  -5  22   9   2   1>0 and 12>8: true, so swap, loop
index:  0   1   2   3   4   5

        i
 data:  8  12  -5  22   9   2   0>0 false, skip comparison of data, end loop
index:  0   1   2   3   4   5

Let us also illustrate at a later time through the inner loop, when the 9 is moved into position from index j = 4, so i starts at 4.

                      ? i
 data: -5   8  12  22 > 9   2  4>0 and 22>9: true, so swap, loop
index:  0   1   2   3   4   5

                  ? i
 data: -5   8  12 > 9  22   2  3>0 and 12>9: true, so swap, loop
index:  0   1   2   3   4   5

              ? i
 data: -5   8 > 9  12  22   2  2>0 and 8>9: false, end inner loop
index:  0   1   2   3   4   5

The 9 started at index j = 4, and now the list is sorted up through index 4.

This will require as many exchanges as Bubble Sort, since only one inversion is removed per exchange. So Insertion Sort also requires \(O(N^2)\) exchanges. On average Insertion Sort requires only half as many comparisons as Bubble Sort, since the average distance an element must move for random input is one-half the length of the sorted portion.

12.4.5. Shell Sort

Shell Sort is basically a trick to make Insertion Sort run faster. If you take a quick glance at the code and look beyond the presence of two additional outer loops, you’ll notice that the code looks very similar.

Since Insertion Sort removes one inversion per exchange, it cannot run faster than the number of inversions in the data, which in worst case is \(O(N^2)\). Of course, it can’t run faster than N, either, because it must look at each element, whether or not the element is out of position. We can’t do any thing about the lower bound O(N), but we can do something about the number of steps to remove inversions.

The trick in Shell Sort is to start off swapping elements that are further apart. While this may remove only one inversion sometimes, often many more inversions are removed with intervening elements. Shell Sort considers the subsequences of elements spaced k elements apart. There are k such sequences starting at positions 0 through k-1 in the array. In these sorts, elements k positions apart are exchanged, removing between 1 and 2(k-1)+1 inversions.

Swapping elements far apart is not sufficient, generally, so a Shell Sort will do several passes with decreasing values of k, ending with k=1. The following examples experiment with different series of values of k.

In this first example, we sort all subsequences of elements 8 apart, then 4, 2, and 1. Please note that these intervals are to show how the method works–not how the method works best.

/// Shell sort of data using specified swapping intervals.
public static void IntArrayShellSort (int[] data, int[] intervals)
{
   int N = data.Length;
   // The intervals for the shell sort must be sorted, ascending
   for (int k=intervals.Length-1; k>=0; k--) {
      int interval = intervals[k];
      for (int m=0; m<interval; m++) {
         for (int j=m+interval; j<N; j+=interval) {
            for (int i=j; i>=interval && data[i]<data[i-interval];
                  i-=interval) {
               Exchange (data, i, i - interval);
            }
         }
      }
   }
}

public static void IntArrayShellSortNaive (int[] data)
{
   int[] intervals = { 1, 2, 4, 8 };
   IntArrayShellSort (data, intervals);
}

In general, shell sort with sequences of jump sizes that are powers of one another doesn’t do as well as one where most jump sizes are not multiples of others, mixing up the data more. In addition, the number of intervals must be increased as the size of the array to be sorted increases, which explains why we allow an arbitrary array of intervals to be specified.

Without too much explanation, we show how you can choose the intervals differently in an improved shell sort, where the intervals have been chosen so as not to be multiples of one another.

Donald Knuth has suggested a couple of methods for computing the intervals:

\[ \begin{align}\begin{aligned}h_0 = 1\\h_{k+1} = 3 h_k + 1\\t = \lfloor log_3 n \rfloor - 1\end{aligned}\end{align} \]

Here we are using notation for the floor function \(\lfloor x \rfloor\) means the largest integer \(\le x\).

This results in a sequence 1, 4, 13, 40, 121…. You stop computing values in the sequence when \(t = log_3 n - 1\). (So for n=50,000, you should have about 9-10 intervals.)

For completeness, we note that \(log_3 n\) must be sufficiently large (and > 2) for this method to work. Our code ensures this by taking the maximum of \(log_3 n\) and 1.

Knuth also suggests:

\[ \begin{align}\begin{aligned}h_0 = 1\\h_{k+1} = 2 h_k + 1\\t = \lfloor log_2 n \rfloor - 1\end{aligned}\end{align} \]

This results in a sequence 1, 3, 7, 15, 31….

Here is the improvement to our naive method that dynamically calculates the intervals based on the first suggestion of Knuth:

/// Generates the intervals for Shell sort on a
/// list of length n via an algorithm from Knuth.
static int[] GenerateIntervals (int n)
{
   if (n < 2) {  // no sorting will be needed
      return new int[0];
   }
   int t = Math.Max (1, (int)Math.Log (n, 3) - 1);
   int[] intervals = new int[t];
   intervals [0] = 1;
   for (int i=1; i < t; i++)
      intervals [i] = 3 * intervals [i - 1] + 1;
   return intervals;
}

public static void IntArrayShellSortBetter (int[] data)
{
   int[] intervals = GenerateIntervals (data.Length);
   IntArrayShellSort (data, intervals);
}

Shell sort is a complex sorting algorithm to make “work well”, which is why it is not seen often in practice. It is, however, making a bit of a comeback in embedded systems.

We nevertheless think it is a very cool algorithm to have heard of as a computer science student and think it has promise in a number of situations, especially in systems where there are limits on available memory (e.g. embedded systems).

12.4.6. Quicksort a.k.a. Partition Sort

This sort is a more advanced example that uses recursion. We list it because it is one of the best sorts for random data, having an average time behavior of \(O(N \log N)\). Quicksort is a rather interesting case. While it has an excellent average behavior, it has a worst case performance of \(O(N ^2)\).

/// Sort elements of data in index range [lowI, highI].
public static void IntArrayQuickSort (int[] data,
                                      int lowI, int highI)
{
   int afterSmall = lowI, beforeBig = highI;
   int pivot = data[(lowI + highI) / 2];
   // in loop data[i] <= pivot if i < afterSmall
   //         data[i] >= pivot if i > beforeBig
   //         region with aftersmall <= i <= beforeBig
   //             shrinks to nothing.
   while (afterSmall <= beforeBig) {
      while (data[afterSmall] < pivot)
         afterSmall++;
      while (pivot < data[beforeBig])
         beforeBig--;
      if (afterSmall <= beforeBig) {
         Exchange (data, afterSmall, beforeBig);
         afterSmall++;
         beforeBig--;
      }
   }  // after loop: beforeBig < afterSmall, and
   //      data[i] <= pivot for i <= beforeBig,
   //      data[i] == pivot for i if beforeBig < i < afterSmall,
   //      data[i] >= pivot for i >= afterSmall.
   if (lowI < beforeBig) // at least two elements
      IntArrayQuickSort (data, lowI, beforeBig);
   if (afterSmall < highI) // at least two elements
      IntArrayQuickSort (data, afterSmall, highI);
}

public static void IntArrayQuickSort (int[] data)
{
   if (data.Length > 1)
      IntArrayQuickSort (data, 0, data.Length - 1);
}

Though the initial call is to sort an entire array, this is accomplished by dealing with sections, so the main work is done in the version with the two extra parameters, giving the lowest and highest index considered.

It picks an arbitrary element as pivot, and then swaps elements with values above and below the pivot until the part of the array being processed is in three sections:

1. elements <= pivot;

2. possibly an element equal to pivot

3. elements >= pivot.

Though sections 1 and 3 are not sorted, there are no inversions between any two separate sections, so only the smaller sections 1 and 3 need to be sorted separately, and only then if they have at least two elements. They can be sorted by calling the same function, but with a smaller range of indices to deal with in each case. These recursive calls stop when a part is reduced to one element.

Another optional glimpse at an advanced topic: The outer while loop in lines 11-20 has fairly complicated logic. To prove it is correct overall, you can state and prove the simpler loop invariant expressed in the comments above the loop, lines 7-10. This allows the conclusion after the loop in comment lines 21-24.

Footnotes

[1]

For a full theoretical treatment, we recommend the outstanding textbook by Niklaus Wirth: Algorithms + Data Structures = Programs, Prentice Hall, 1976, who invented the Pascal language. Also adapted are some examples from Thomas W. Christopher’s animated sorting algorithms page.