Sorting

This list of names is not in order:

names = ['Torvalds', 'Zuckerberg', 'Lovelace', 'Turing', 'Johnson']

But if we want to print it in alphabetical order? We need to sort the list, which Python can do for us:

print(sorted(names))

But this function "sorted" is not magic. In this section, we will build it ourselves.

A sorting algorithm

An algorithm is a list of instructions to be executed to achieve a certain goal or produce a certain result - just like a recipe for baking a cake. When we write our code, we explain these steps in a language that machines understand. The following video talks about algorithm in Swedish with an English translation:

Our list of names is sorted when all names are in alphabetical order. We know of course which name should come first, but we can also compare two strings as we compare numbers using the smaller than (<) and greater than (<) symbols:

print('Lovelace' < 'Turing') 

print('Turing' > 'Lovelace')

Both instructions will print True - because Lovelace (beginning with L) should appear before Turing (starting with T).

Our goal is to get the entire list in order, but how do we get there? Even if we can sort a list in our heads, it can be difficult to instruct a computer to do it.

All steps needed to reach our goal of a sorted list constitute a sorting algorithm. There are many available, each with their own pros and cons. Here, we'll look at one called Bubblesort:

The idea is as follows:

• Pick two names next to each other.
• If they are in the wrong order, swap them.

After that, the list will be at least a little better sorted than before. That means, if we do this enough times, eventually the whole list will be sorted.

Bubblesort in Python

This is how we would carry out Bubblesort using Python:

# Go through the list from start to end using a for-loop
# Compare each pair of names next to each other
# If they are in the wrong order, swap them

That can be written as follow:

Compare the first output to the second, you can see it's now a little better than before!

What we need now is to run this several times, and continually get a slightly more sorted list than before. By putting the for loop inside another for-loop we can achieve exactly this.

The final program looks like this:

names = ['Torvalds', 'Zuckerberg', 'Lovelace', 'Turing', 'Johnson'] 

print("Unsorted version:") 
print(names) 

for j in range(0, len(names)): 
    for i in range(0, len(names) - 1): 
        if names[i+1] < names[i]: 
            names[i], names[i+1] = names[i+1], names[i] 

print("Sorted version:") 
print(names)