Sorting Fundamentals: Part 1
Ever since computers were invented people have been interested in sorting collections of items. It's useful in itself plus it is also a pre-requisite for efficiently implementing other functionality like searching and merging.
There are a myriad of different ways to implement sorting each with it's pros and cons. Whilst many programmers consider sorting a solved problem, it's still useful to understand the fundamentals so that you are able to make the necessary trade-offs when faced with a decision about which sorting technique to use (or are curious about which technique the major frameworks use in their sorting routines). Accordingly, the paragraphs that follow discuss the more well-known sorting techniques giving implementation details in both Java and C#, and noting their efficiency using complexity theory ("Big O notation").
Bubble Sort
Perhaps the most (in)famous sorting algorithm is the bubble sort. This algo uses pairwise comparisons to shuffle "bigger" items to the right (or "smaller" items to the left). Unless the data is already sorted, a bubble sort needs to make multiple passes through the data set to sort it.
In Java, this is how it can be implemented:
1: public static void bubbleSort(int[] input)
2: {
3: for(int i=input.length-1; i>=0; i--)
4: {
5: int swaps=0;
6: for(int j=0; j<i ;j++)
7: {
8: if (input[j] > input[j+1])
9: {
10: int temp = input[j];
11: input[j] = input[j+1];
12: input[j+1] = temp;
13: swaps++;
14: }
15: }
16: if (swaps==0)
17: return;
18: }
19: }
Note that the input is an array of integers. We use the primitive type here because unlike C# which has a unified type system, Java has different constructs for primitives and class types, and regrettably the performance characteristics of the non-primitive types is not as good as the primitive types. Hence we use an array of primitives here.
Generally we are interested in two performance characteristics: asymptotic running time, and space complexity. Other considerations such as stability are sometimes important but here we'll focus on run time and space complexity. [Stability means the equivalent elements retain their relative positions, after sorting. In fact, any sorting algorithm can be made stable at the cost of O(n) extra space, and moderately increased run time.]
Run Time Complexity
For run time complexity we are concerned with the asymptopic upper bound on the number of comparisons needed. From the code above, it should be obvious that for an input array of length n, in the worst case a total of (n-1) passes are made and the total number of comparisons needed is: (n-1) + (n-2) +... + 2 + 1. This is the sum of an arithmetic progression and reduces to n*(n-1)/2. This expands to a polynomial with n2 being the highest term. Hence we say the running time is ~O(n2). We don't worry about constant factors, the co-efficients or other lower-order terms - it's the dominant term that concerns us. In this case, a quadratic running time is not particularly efficient when n is large. The best case occurs when the input is already sorted in which case the swap counter check in lines 16 and 17 ensures that we only need to do n-1 comparisons which leads to running time ~O(n).
Apart from the best and worst cases, it is also useful to understand the average case. The average case running time is the expected running time when the input is randomly drawn from a given distribution (hence you need to ask yourself "what input distribution"). Thus knowledge of all possible input sequences, the probability of these sequences occurring, and the individual running times for all these possible sequences is required to obtain the average case running time. In general we assume the Uniform distribution, since in the absence of other information we assume all possible sequences are equally likely. This is why the uniform distribution is also referred to as the distribution of maximum ignorance.
To derive the average case for the bubble sort we need to identify the total number of comparisons required for the n-1 passes and then divide this sum by n-1. This is because the algorithm bails out as soon as it has one pass in the inner loop that has no swaps. That indicates that the remainder of the list is sorted and no further comparisons are needed. We are, of course, assuming that we have an equal chance of bailing out after each of the n-1 passes in the outer loop. The maths of this calculation is easily done if we represent the comparison count for each scenario. Assuming n=5, here is a table showing the comparison count for each of the 4 passes.
| Comparisons Needed | |||||
| Passes Needed | 1st Pass | 2nd Pass | 3rd Pass | 4th Pass | Total |
| 1 | n-1 | n-1 | |||
| 2 | n-1 | n-2 | (n-1) + (n-2) | ||
| 3 | n-1 | n-2 | n-3 | (n-1) + (n-2) + (n-3) | |
| 4 | n-1 | n-2 | n-3 | n-4 | (n-1) + (n-2) + (n-3) + (n-4) |
So to sum all of these it is easiest to consider each column and realise that the sum of the far right column yields a polynomial whose highest order of n is 2. Thus the average run time complexity is also ~O(n2).
With an average case and worst case run time complexity of O(n2), clearly the bubble sort is not at all efficient. Really, you should never use this sort. It's included here merely for completeness. The chart below shows, even for small cases of n (shown on the x-axis), how much faster quadratic run time (the green line) grows compared to other growth rates.
Space Complexity
The bubble sort code does an in-place sort, meaning that only a small, fixed amount of additional memory is required and the original item array is used to store the sorted array. Thus we say that the worst case space complexity ~ O(n) with O(1) auxiliary memory. This is as efficient as it gets.
Other Languages
The multi-lingual reader will note that the above Java code works without change in C#. However, in C# we can make use of generics without taking much of a performance hit like we do in Java when we switch from value types (primitives) to reference types. The code shown below employs a generic constraint on the open generic type to ensure that it implements the generic IComparable
1: public static void BubbleSort<T>(T[] input) where T:IComparable<T>
2: {
3: for (var i = input.Length - 1; i >= 0; i--)
4: {
5: var swaps = 0;
6: for (var j = 0; j < i; j++)
7: {
8: if (input[j].CompareTo(input[j + 1]) > 0)
9: {
10: T temp = input[j];
11: input[j] = input[j + 1];
12: input[j + 1] = temp;
13: swaps++;
14: }
15: }
16: if (swaps == 0)
17: return;
18: }
19: }
Of course, we can do a generic version in Java, but as mentioned earlier, the performance of reference types compared to primitives is not great:
1: public static <T extends Comparable<T>> void bubbleSort(T[] input)
2: {
3: for(int i=input.length-1; i>=0; i--)
4: {
5: int swaps=0;
6: for(int j=0; j<i ;j++)
7: {
8: if (input[j].compareTo(input[j+1]) > 0)
9: {
10: T temp = input[j];
11: input[j] = input[j+1];
12: input[j+1] = temp;
13: swaps++;
14: }
15: }
16: if (swaps==0)
17: return;
18: }
19: }
Selection Sort
The selection sorting algorithm examines all of the unplaced items, picks out the minimum (or maximum) item, places it, then repeats this cycle until all items have been placed. To "place the item" we swap it with the (unplaced) item in the position that we are trying to fill. In Java, it looks like this:
1: public static void selectionSort(int[] input)
2: {
3: for(int i=0; i<input.length; i++)
4: {
5: int minIndex = i;
6: for(int j=i+1; j<input.length; j++)
7: {
8: if (input[j] < input[minIndex])
9: minIndex =j;
10: }
11: if (minIndex != i)
12: {
13: int temp = input[i];
14: input[i] = input[minIndex];
15: input[minIndex]=temp;
16: }
17: }
18: }
Or if you want the generic version in Java:
1: public static<T extends Comparable<T>> void selectionSort(T[] input)
2: {
3: for(int i=0; i<input.length; i++)
4: {
5: int minIndex = i;
6: for(int j=i+1; j<input.length; j++)
7: {
8: if (input[j].compareTo(input[minIndex]) < 0)
9: minIndex =j;
10: }
11: if (minIndex != i)
12: {
13: T temp = input[i];
14: input[i] = input[minIndex];
15: input[minIndex]=temp;
16: }
17: }
18: }
And lastly in C#:
1: public static void SelectionSort<T>(T[] input) where T:IComparable<T>
2: {
3: for(int i=0; i<input.Length; i++)
4: {
5: int minIndex = i;
6: for(int j=i+1; j<input.Length; j++)
7: {
8: if (input[j].CompareTo(input[minIndex]) < 0)
9: minIndex =j;
10: }
11: if (minIndex != i)
12: {
13: T temp = input[i];
14: input[i] = input[minIndex];
15: input[minIndex]=temp;
16: }
17: }
18: }
Run Time Complexity
As you can see this uses nested loops leading to a worst case running time complexity ~ O(n2). You cannot take any short cuts when you need to find the minimum (or maximum) item in a collection, hence the best and average running times are also ~ O(n2) using our knowledge of arithmetic progressions (on the first pass you need to compare n-1 items to get the minimum/maximum, on the next pass n-2 items, then n-3, etc). So this sort isn't any better, asymptotically, than the bubble search. i.e it's not particularly efficient either.
Space Complexity
Again the code does an in-place sort, implying that the worst case space complexity ~ O(n) with O(1) auxiliary memory.
Insertion Sort
This approach works by inserting each item into an already sorted sub-list. With careful implementation it can be implemented in-place as follows (in Java):
1: public static void insertionSort(int[] input)
2: {
3: for(int i=1; i<input.length; i++)
4: {
5: int current = input[i];
6: int j=i-1;
7: while(j>=0 && current < input[j])
8: {
9: input[j+1] = input[j];
10: j--;
11: }
12: input[j+1] = current;
13: }
14: }
And if you prefer a generic Java variety:
1: public static<T extends Comparable<T>> void insertionSort(T[] input)
2: {
3: for(int i=1; i<input.length; i++)
4: {
5: T current = input[i];
6: int j=i-1;
7: while(j>=0 && (current.compareTo(input[j]) < 0))
8: {
9: input[j+1] = input[j];
10: j--;
11: }
12: input[j+1] = current;
13: }
14: }
And for completeness, here it is in C#:
1: public static void InsertionSort<T>(T[] input) where T:IComparable<T>
2: {
3: for(int i=1; i<input.Length; i++)
4: {
5: T current = input[i];
6: int j=i-1;
7: while(j>=0 && (current.CompareTo(input[j]) < 0))
8: {
9: input[j+1] = input[j];
10: j--;
11: }
12: input[j+1] = current;
13: }
14: }
Run Time and Space Complexity
This also has quadratic worst case running time, O(n2). As to be expected, the best case happens when the input is already sorted. In that case the inner while loop will only ever do 1 comparison which implies O(n) running time for the best case.
In this case, perhaps the hardest metric to identify is the average case. To derive the average case run time complexity first consider that the outer loop must perform n-1 iterations. On the first iteration of the outer loop there is 1 item in the sorted sub-list, the index 0 item, that we will compare the current item, the index 1 item, to. On the second iteration we have 2 items, the index 0 and 1 items, in the sorted sub-list that we compare to the current item, the index 2 item. Thus we can say that on pass j of the outer loop we will have j items in the sorted sub-list. Thus the number of comparisons required in the inner while loop could be anything in the set {1,2,3,...,j}. The average number of comparisons for pass j is given by:
So the overall average number of comparisons is given by:
Thus the average case run time is also quadratic.
With respect to space complexity, again the analysis is pretty easy. Because it is in-place the worst case space complexity ~ O(n) with O(1) auxiliary memory.
Although the insertion sort is efficient when the input is "almost sorted", for all practical purposes none of these sort techniques are particularly good when the array/collection to sort is "large". There is a family of algorithms that employ divide-and-conquer techniques that have significantly better run time complexity than those mentioned above. More on those in Part 2...
08 Jun 2009 Damien Wintour 2 comments
