Sorting Algorithms

I think just about everyone reading this chapter will have, at some point, gone on an online shopping portal—whether it was for clothes, school supplies, books, or anything else is of little consequence. Often major shopping websites will have hundreds or thousands of unique items for sale, which can make it difficult to find something you actually want to buy. Because of this, online retailers will allow users to apply filters to their catalogue, letting them look for only such-and-such size or such-and-such brand. Additionally, these websites will also include the ability to order the items by price from highest-to-lowest or lowest-to-highest. This dynamic ordering of items within a program is handled by sorting algorithms—routines which have been created to place elements in either decreasing or increasing magnitude. There are many different sorting algorithms in use today, but in this class we will only focus on three: selection sort, insertion sort, and bubble sort.

Selection sort, like all of the sorts shown in this chapter, is an intuitive sorting algorithm with a simple implementation. We divide an array of values into a sorted and unsorted portion and keep track of each portion. The sorted portion holds a space for a new value to be swapped into it and the unsorted portion is swept to find the smallest element in it. The index of the smallest element is recorded so it can be swapped into the smallest portion. A visualization can be found below:

Initial:  [ 12 |  5 |  3 | 10 |  7 ]
           i=0

Pass 1: find minimum in [0..4]
          [ 12 |  5 |  3 | 10 |  7 ]
            i=0  j=1  j=2  j=3  j=4
                      ^
                      min found at j=2 (value 3)

          swap arr[i=0] with arr[j=2]

          [  3 |  5 | 12 | 10 |  7 ]
            *               (sorted)

Pass 2: find minimum in [1..4]
          [  3 |  5 | 12 | 10 |  7 ]
                 i=1  j=2  j=3  j=4
                 ^
                 min found at j=1 (value 5, already in place)

          swap arr[i=1] with arr[j=1] (no change)

          [  3 |  5 | 12 | 10 |  7 ]
             *    *              (sorted)

In the above visualization, i denotes the index of the last element of the sorted portion, and j denotes indices of the unsorted portion. The selection in selection sort is the finding of the minimum and selecting it for swapping.

I leave it as an exercise for the reader to finish out the above visualization, as well as to try and implement selection sort in Java.

Insertion sort is very similar to selection sort. Here, we also partition the array into a sorted and unsorted portion. The biggest difference is that we are not selecting an element to end up at the end of the sorted portion, but we actually update the sorted portion with a new element which is propogated down stream if necessary. We can see insertion sort playing out visually below:

Initial:  [ 12 |  5 |  3 | 10 |  7 ]

Pass 1: insert arr[1]=5 into sorted region [0..0]
          [ 12 |  5 |  3 | 10 |  7 ]
            i=0  j=1
          5 < 12, shift 12 right
          [  5 | 12 |  3 | 10 |  7 ]
             *              (sorted)

Pass 2: insert arr[2]=3 into sorted region [0..1]
          [  5 | 12 |  3 | 10 |  7 ]
                      j=2
          3 < 12, shift 12 right
          [  5 |  3 | 12 | 10 |  7 ]
                 j=1
          3 < 5, shift 5 right
          [  3 |  5 | 12 | 10 |  7 ]
            j=0 (reached beginning, insert here)
             *    *              (sorted)

Pass 3: insert arr[3]=10 into sorted region [0..2]
          [  3 |  5 | 12 | 10 |  7 ]
                           j=3
          10 < 12, shift 12 right
          [  3 |  5 | 10 | 12 |  7 ]
                      j=2
          10 > 5, insert here
          [  3 |  5 | 10 | 12 |  7 ]
             *    *    *              (sorted)

i and j function identically to what they did in selection sort, the unsorted and sorted indices, respectively. The difference here is that you can see that when a value is placed in the sorted portion, it is swapped with other elements downstream. This guarantees that at the end of a full pass the sorted portion actually is sorted.

Again, I leave it as an exercise for the reader to finish out the above visualization, as well as to try and implement insertion sort in Java.

Bubble sort is likely the most intuitive sorting algorithm out there. Most beginner programmers implement bubble sort naturally without referring to any textbooks on the matter. All we do is progressively swap values of the array if they need to be swapped. Essentially we start from the beginning of the array and "float" values up. We continue to do this until we do a full pass of the array without a single swap:

Initial:  [ 12 |  5 |  3 | 10 |  7 ]

Pass 1: bubble largest element to end
          [ 12 |  5 |  3 | 10 |  7 ]
            j=0  j=1
          12 > 5, swap
          [  5 | 12 |  3 | 10 |  7 ]
                 j=1  j=2
          12 > 3, swap
          [  5 |  3 | 12 | 10 |  7 ]
                      j=2  j=3
          12 > 10, swap
          [  5 |  3 | 10 | 12 |  7 ]
                           j=3  j=4
          12 > 7, swap
          [  5 |  3 | 10 |  7 | 12 ]
                                  *   (sorted)

Pass 2: bubble largest remaining to end
          [  5 |  3 | 10 |  7 | 12 ]
            j=0  j=1
          5 > 3, swap
          [  3 |  5 | 10 |  7 | 12 ]
                 j=1  j=2
          5 < 10, no swap
          [  3 |  5 | 10 |  7 | 12 ]
                      j=2  j=3
          10 > 7, swap
          [  3 |  5 |  7 | 10 | 12 ]
                           j=3  j=4
          10 < 12, no swap
          [  3 |  5 |  7 | 10 | 12 ]
                            *    *  (sorted)

Again, I leave it as an exercise for the reader to finish out the above visualization, as well as to try and implement bubble sort in Java.

We've seen above that every algorithm shown above does exactly the same thing in terms of results. We always end with an array that was sorted in increasing order. Why then do we bother using more than one algorithm? The answer is found in an analysis of algorithmic complexity, which I will have more to say on a bit later. Suffice it to say that sometimes a certain algorithm will be better for one job in certain situations than another.

As an example, we will compare selection sort and bubble sort in two different contexts. One where our numbers are already sorted, and another where they are sorted in reverse order. Each case will look at arrays with half a million elements (from [1-500,000] and [500,000, 1]).

You can see the Java program I used to test the algorithms here:

 1: import java.util.Arrays;
 2: public class Sorting{
 3:     static final int SIZE = 500_000;
 4: 
 5:     public static void swap(int[] arr, int a, int b){
 6:         int temp = arr[a];
 7:         arr[a] = arr[b];
 8:         arr[b] = temp;
 9:     }
10: 
11:     public static void main(String[] args){
12:         if(args.length != 2){
13:             System.out.printf("\"selection\" for Selection Sort%n\"insertion\" for Insertion Sort%n\"bubble\" for Bubble Sort%n\"desc\" for descending array %n \"asc\" for ascending array%n");
14:             System.exit(1); //Error out
15:         }
16:         int[] arr = new int[SIZE];
17:         switch(args[1]){
18:         case "desc":
19:             for(int i = 0; i < SIZE; i++){
20:                 arr[i] = SIZE - (i);
21:             }
22:             break;
23:         case "asc":
24:             for(int i = 0; i < SIZE; i++){
25:                 arr[i] = i+1;
26:             }
27:             break;
28:         default:
29:             throw new RuntimeException("desc or asc!");
30:         }
31: 
32:         long start = System.currentTimeMillis();
33:         switch(args[0]){
34:         case "selection":
35:             System.out.printf("Selection Sort: ");
36:             SelectionSort.sort(arr);
37:             break;
38:         case "insertion":
39:             System.out.printf("Insertion Sort: ");
40:             InsertionSort.sort(arr);
41:             break;
42:         case "bubble":
43:             System.out.printf("Bubble Sort: ");
44:             BubbleSort.sort(arr);
45:             break;
46:         default:
47:             throw new RuntimeException("No valid sort selected");
48:         }
49:         double duration = (System.currentTimeMillis() - start) / 1_000.0;
50:         System.out.printf("%.2f s%n", duration);
51:     }
52: }

Let's see how bubble sort and selection sort do with a descending list:

josephraskind@stargazer:/tmp/sorting$ javac Sorting.java; java Sorting selection desc
Selection Sort: 117.79 s
josephraskind@stargazer:/tmp/sorting$ javac Sorting.java; java Sorting bubble desc
Bubble Sort: 93.51 s

We can see there's some parity in the performance. Bubble sort is a bit faster but proportionally only a ~1.3X speedup. If I were to run this test 100 times we would likely see that decrease on average as well. What about on an ascending list:

josephraskind@stargazer:/tmp/sorting$ javac Sorting.java; java Sorting selection asc
Selection Sort: 33.76 s
josephraskind@stargazer:/tmp/sorting$ javac Sorting.java; java Sorting bubble asc
Bubble Sort: 0.02 s

Wow, that's a ~1700X speedup! This is because the list is already sorted, so the bubble sort never has to float up a single value, we only loop through the array once whereas selection sort still has to loop through every element in the array.

All sorting algorithms have this kind of give and take.

1. The chapter shows the first three passes of selection sort on [12, 5, 3, 10, 7]. Complete the visualization for passes 4 and 5 by hand, showing the values of i and j at each step. Then implement selection sort in Java and verify your hand trace matches the output of your program.
2. The chapter shows the first three passes of insertion sort on [12, 5, 3, 10, 7]. Complete the visualization for passes 4 and 5 by hand. Then implement insertion sort in Java and verify your hand trace matches the output of your program.
3. The chapter shows the first two passes of bubble sort on [12, 5, 3, 10, 7]. Complete the visualization for passes 3, 4, and 5 by hand, noting which comparisons result in swaps and which do not. Then implement bubble sort in Java and verify your hand trace matches the output of your program.
4. Implement all three sorting algorithms in a single Java program. Add a counter to each that tracks the total number of comparisons made when sorting [12, 5, 3, 10, 7]. Which algorithm makes the fewest comparisons on this input? Does the winner change if you sort the already-sorted array [3, 5, 7, 10, 12]?
5. The chapter states that bubble sort performs poorly on nearly-sorted arrays in its basic form. Add an optimization: if no swaps were made during an entire pass, the array is already sorted and the algorithm can terminate early. Implement this optimization and verify it causes bubble sort to terminate in a single pass on [3, 5, 7, 10, 12].
6. Implement selection sort on a String[] instead of an int[]. Use String's compareTo method to compare elements. Sort the array ["banana", "apple", "date", "cherry", "elderberry"] and print the result. What does compareTo return and how do you use its return value to determine ordering?
7. The chapter motivates sorting through the online shopping analogy. Consider a list of BankAccount objects from earlier in the course. Write a program that sorts an array of BankAccount objects by balance from lowest to highest using insertion sort. What challenge do you encounter that did not exist when sorting integers?
8. The chapter shows that sorting requires comparing elements against each other. For each of the three algorithms, count the exact number of comparisons made when sorting [12, 5, 3, 10, 7] by hand using the visualizations from the chapter. Then count the comparisons again on the reverse-sorted array [12, 10, 7, 5, 3] and on the already-sorted array [3, 5, 7, 10, 12]. Which algorithm's comparison count changes the most between the best and worst case? Which changes the least? What does this suggest about which algorithm you would choose if you knew your data was already nearly sorted?
9. The chapter shows that sorting is motivated by the need to order data for human consumption. Consider the following scenario: a teacher has an array of student grades and wants to find the median grade. Write a program that uses one of the three sorting algorithms to find the median of [72, 95, 61, 88, 79, 55, 90]. Why is sorting a useful first step for finding the median?
10. The chapter introduces three sorting algorithms that all sort in place—they rearrange the elements of the original array rather than creating a new one. Write a version of selection sort that instead returns a new sorted array without modifying the original. What additional steps are required? Verify that the original array is unchanged after calling your method.