# 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)
```

**Read page in other languages**

In this video, we talk about a type of algorithm (sorting algorithms) by implementing the famous "Bubblesort".

**Algorithm**: A description for how to solve a problem. A recipe is an example of an algorithm for cooking a certain dish. Programming is writing code to carry out steps of an algorithm.**Bubblesort:**One (of many) algorithms for sorting the contents of a list.**List:**A list is a collection of data in order. Can also be known as "**array**" in other programming languages.**for-loop**: One type of loop/repetition that fits well for a predetermined number of steps.

**Difficulty level**