Sorting Algorithms

LEARNING OBJECTIVES

After this lesson, you will be able to:

Explain Bubble Sort, Insertion Sort
Explain your decision behind what sorting algorithm should be used for a given problem

STUDENT PRE-WORK

Before this lesson, you should already be able to:

Write Java functions that accepts input and iterates over data collections

INSTRUCTOR PREP

Before this lesson, instructors will need to:

Open/run the starter and solution code for this lesson and adapt as needed

Opening (5 mins)

Sorting data is a common operation. Whether we are sorting by numerical value, alphabetical order, or some custom definition, we need a way to organize and order our data. For example, what if you are writing a fantasy sports app, and you want to be able to list all of the leaders by a certain statistical category? Sorting algorithms will help you do that.

An algorithm is defined simply as a procedure or formula used to solve a problem. In this case, the problem is we want our unsorted data to be sorted. Fortunately for us, several formulas have already been written to solve this problem.

Check: In pairs, take 30 seconds to discuss why developers need more than one sorting algorithm if all sorting algorithms have the same end goal. Share out.

Guided Practice: Bubble Sort (15 mins)

One of the simplest sorting algorithms is called Bubble Sort. Bubble Sort works in just a few steps:

1) Start at the beginning of an array (or list) 2) Compare the current item to the next 3) Swap them if the current item is greater than the next 4) Go to the next item 5) Repeat steps 1-4 until no swaps take place

Check: What are some potential pros and cons of this method?

Some pros of Bubble Sort are:

1) Simple to implement 2) Very fast on data that is already mostly sorted

The largest disadvantage of using Bubble Sort is that it is much slower than other algorithms when working with data that isn't already mostly sorted, as it may require a lot of iterations through the list.

Here is an example of how Bubble Sort operates on the array {5, 1, 4, 2, 8} (Source: https://en.wikipedia.org/wiki/Bubble_sort):

First Pass

( 5 1 4 2 8 ) --> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.

( 1 5 4 2 8 ) --> ( 1 4 5 2 8 ), Swap since 5 > 4

( 1 4 5 2 8 ) --> ( 1 4 2 5 8 ), Swap since 5 > 2

( 1 4 2 5 8 ) --> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

Second Pass

( 1 4 2 5 8 ) --> ( 1 4 2 5 8 )

( 1 4 2 5 8 ) --> ( 1 2 4 5 8 ), Swap since 4 > 2

( 1 2 4 5 8 ) --> ( 1 2 4 5 8 )

Now, the array is already sorted, but the algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

Third Pass

( 1 2 4 5 8 ) --> ( 1 2 4 5 8 )

Check: Discuss with the person next to you if you see anything wrong with the third pass. How could this algorithm be improved?

Demo: The Bubble Sort Algorithm (5 mins)

Let's take a look at some pseudocode for Bubble Sort:

func bubblesort( var a as array )
    for i from 1 to N
        for j from 0 to N - 1
           if a[j] > a[j + 1]
              swap( a[j], a[j + 1] )
end func

As you can see, it is a pretty basic, nested for loop that just compares each element to the element that follows. Then, the pseudocode swaps the two elements if the original element is greater than the next.

Independent Practice: Bubble Sort in Java - Optimized (15 mins)

Now, you're going to write Java code to implement the pseudocoded algorithm above. For a small optimization, think about how you could know the algorithm is complete without having to run the nested for loops - once this has been achieved, have the algorithm quit.

Use the starter code provided to get started:

public static void main(String[] args) {
    int[] unsorted = {10, 15, 1, 3, 14, 2, 17, 9, 51, 6, 16, 22, 8};
    bubbleSort(unsorted);

    for(int i = 0; i < unsorted.length; i++) {
        System.out.println(unsorted[i]);
    }
}

private static void bubbleSort(int[] unsorted) {
    //Your code here. Include a print statement
    //declaring after which pass (iteration through
    //the outside loop) the algorithm. It should be the 9th.        
}

Check: Have students share their solutions in the last 3 minutes.

Introduction: Insert Sort (15 mins)

Insert Sort is another relatively simple sorting algorithm. Like Bubble Sort, it works best on arrays and lists that are already mostly sorted. It is faster and more optimized than Bubble Sort, especially on smaller lists. Insert Sort works by iterating through the list or array and inserting each element where it belongs in the collection being built behind it.

Here is how Insert Sort works on the same array that we sorted above:

( 5 1 4 2 8 ) --> ( 1 5 4 2 8 ), Here, the algorithm starts at the second element and iterates backwards until it finds where the element fits. In this case, the element goes before 5

( 1 5 4 2 8 ) --> ( 1 4 5 2 8 ), Now, the algorithm goes to the 3rd element and finds that it belongs between 1 and 5

( 1 4 5 2 8 ) --> ( 1 2 4 5 8 ), Element #4, 2, belongs between 1 and 4

( 1 4 2 5 8 ) --> ( 1 4 2 5 8 ), Now, because all of the elements are already in order, no change is made.

Basically, Insert Sort works by going forward through an array one time, stopping at each element to look behind it to find the proper place for that element. This sort of operation requires nested for loops, which is why Insert Sort is known as a quadratic sorting algorithm.

Quadratic Functions

Consider the formula in the graph below:

Because the term "quad" can refer to a square, and the variable in this equation gets squared (x^2), we refer to this equation as a Quadratic Equation.

Instructor note: Slowly, explain why the Insert Sort algorithm is considered a quadratic equation. Insert Sort is referred to as quadratic because the number of steps in the algorithm increases as a quadratic function of the size of the list.

Check: In pairs, take a minute to discuss another example of a quadratic sorting algorithm.

Guided Practice: The Insert Sort Algorithm (10 mins)

Now, as a class, let's come up with the pseudocode for Insert Sort.

Instructor Note: Do this as a class discussion, prompting students for each line and providing hints where necessary.

func insertionSort( var a as array )
    for i from 1 to N
        for j from i to 1
            if a[j] < a[j-1]
                swap a[j] and a[j-1]
end func

Independent Practice: Implement Insertion Sort (15 mins)

Note: This can be a pair programming activity or done independently.

Your turn! Implement Insert Sort to sort an array of integers. Print each swap after it occurs to better see how Insert Sort reorders the elements. Use the starter code provided to get started:

public static void main(String[] args) {
    int[] unsorted = {7, 3, 2, 4, 9, 1, 14, 12};
    int[] sorted = doInsertionSort(unsorted);

    for(int i = 0; i < sorted.length; i++) {
        System.out.println(sorted[i]);
    }
}

private static int[] doInsertionSort(int[] input) {
    //Your code here
    return input;
}

Check: Students should share their answers with 3 minutes left.

Conclusion (5 mins)

There is no perfect sorting algorithm. There is, however, a perfect time and place for several sorting algorithms. That is why it is necessary to know the properties of several algorithms and how their respective strengths and weaknesses stack up against each other. The two algorithms taught in this lesson both have similar strengths and weaknesses. Unfortunately, neither one does very well with larger, less sorted datasets. For that, we need a more powerful algorithm in future lessons.

Sorting