Discover How to Build Programs With Algorithms

As we’ve seen, computer programs help us resolve simple and complex problems. One of the most common things we need programs for is sorting information. This might seem easy at first glance, but there’s more to it than meets the eye—we also need to think about the most efficient way of doing it.

Sorting a group of 10 numbers from the smallest to the largest is pretty quick. But how about 100,000 numbers? What about when Google needs to sort several hundred gigabytes of emails?

Sorting is what programs do best! We often need to reorganize our data to use it in a different way, so it’s important to know how this works.

Let’s take a look at one of the best-known sorting algorithms—bubble sort.

Understand Bubble Sort

This algorithm steps through a list of elements, comparing adjacent data and swapping them around if the first value is higher than the second. It does this for all pairs of elements in a list, and then starts again at the beginning until all pairs are in the right order.

We can demonstrate this with books. I’m sure that at some point in your life, you’ve sorted your bookcase—whether in alphabetical order, by author, or perhaps in height order. For the purposes of this demonstration, we’ll sort books in order of height.

We’ll start by taking the first book and comparing it to the second. If it’s bigger, we swap them around. Otherwise, we leave them as they are.

When we’ve been through all the books once, the biggest one should be at the end. We then need to start again to put the second biggest one in place.

This process goes on until the bookcase is fully sorted!

So, how do we write this in pseudocode?

We’ll start by writing a function to move through the books one by one. You’re already familiar with this structure—it’s a loop! The loop needs to go round 10 times, as we’re going to step through a list of 10 books, but this time from the first cell to the last.

Bubble sort(array) algorithm
   size ← Size of array
   For i from size - 1 to 1 :
      …
   End For
End

Inside the loop, the books are swapped round if the second is bigger than the first. We can use the conditional structures we’ve already seen.

Bubble sort(array) algorithm
   size ← Size of array
   For i from size - 1 to 1 :
      If array[i+1] < array[i] :
         swap(array[i+1], array[i])
      End If
   End For
End

If we think about it, the number of loops needs to correspond to the square of the number of items remaining to be sorted in the list.

Let’s take the first book as an example. If it’s the biggest, our algorithm will need to execute the loop nine times to move it to the end. But once the book is in its place, it knows that it doesn’t need to go all the way to the end. It can therefore execute the loop eight times, then seven, then six, and so on until it gets to one.

In pseudocode, it would look like this:

Bubble sort(array) algorithm
   size ← Size of array
   For i from size - 1 to 1 :
      For j from 0 to i - 1
         If array[j+1] < array[j] :
            swap(array[j+1], array[j])
         End If
      End For
   End For
End

Discover Other Sorting Algorithms

Bubble sort is the most well-known sorting algorithm, but it’s far from the most efficient! Even in real life, when we sort out a bookcase, we don’t compare each book with the next over and over again! Luckily, there are other algorithms we can use.

If we’re sorting a large bookcase, we might decide to break it down into smaller units and sort them separately before merging them together. Or we could put the biggest and smallest books at the start, at the same time.

We all have our different strategies! There are so many sorting algorithms that it would be impossible to explain all of them here, but this table shows some of the most common ones:

Take a look at the non-exhaustive list of different sorts on this Wikipedia page, and read some of the definitions to find out how they work. 

Over to You!

Context

If you remember, the door to exit the maze is locked with three keys, numbered from 1 to 3. Key 1 opens the highest lock on the door, key 2 opens the lock below, and key 3 opens the bottom lock. We want to be able to sort the bag of keys to arrange them in ascending order, so the player can get them out in the right order when they get to the door.

Instructions

Write the pseudocode for an insertion sort algorithm. Insertion sort compares values two by two, starting with the second value in the list. If this value is higher than the value to its left, no change is made. Otherwise, the value is moved several times to the left until it encounters a value smaller than it.

Your Mission

• Save the size of the array in a variable,  N.

• Move through the array one by one from the second entry to the end. 

• Temporarily save the current element of your iteration.

• Compare this element with all the elements in the sorted sublist.

• Shift all the elements in the sublist by one position if they are greater than the sort element.

• Insert the temporary value.

• Repeat until the list is sorted.

Check Your Work

Here’s the result you should get from this exercise:

Insertion sort(array) algorithm
   N ← Size of array
   For i from 1 to N:
      x ← array[i]
      j ← i-1
      While j >= 0 AND x < array[j]:
         array[j+1] ← array[j]
         j ← j - 1
      End While
      array[j+1] ← x
   End For
End

Let’s Recap!

• Sorting data is an important task, and is often used in software development. 

• There are different types of sort, such as bubble sort, selection sort, insertion sort, and many more.

• Different programs solve different problems, so you need to choose the right sort algorithm for what you want to do.

I’ve explained to you that there are different algorithms for different situations. But why is this? Different problems take more or less time to solve—this is known as the complexity of an algorithm. We’ll see how to calculate this in the next chapter.