Sorting

What you will be able to do

After this lesson you can

• sort a list with sorted and sort, and change the order with reverse and key,
• sort records by one field, or by two,
• write bubble sort and selection sort, and
• say why Python's own sort is the better choice.

Putting things in order

Python can sort for you.

Predict first. Look at sorted(names). Where do you expect asha? Then run it.

• sorted(x) makes a new sorted list. x.sort() sorts x itself and gives back None. Writing numbers = numbers.sort() loses the list.
• reverse=True puts the biggest first.
• key=len sorts by the length of each item. The key is a function that is called for each item, and the items are sorted by what it gives.
• key=str.lower sorts as if all the letters were small. Without it, asha comes last, because in the computer's order all the capital letters come before all the small letters.

Sorting records

Often a list holds pairs, such as a name and a mark. Tuples are compared item by item, from the first. So sorted(students) sorts by the name, and for two equal names, by the mark.

How does sorting work? Bubble sort

You can sort by hand with a simple idea: compare neighbours, and swap them if they are in the wrong order. Repeat until no swap is needed.

The swap numbers[i], numbers[i + 1] = numbers[i + 1], numbers[i] uses the tuple trick that you learned: no third variable is needed.

After 3 passes, 4 items are always in order. In real programs, use sorted(): it is much faster than bubble sort.

Another way: selection sort

Here is a different idea. Find the smallest item of the whole list, and put it first. Then find the smallest of the rest, and put it second. And so on.

Why not always use our own?

Bubble sort and selection sort are easy to understand, and that is their use: they show how sorting works. For 1000 items, they need about half a million comparisons. Python's own sorted uses a much faster method, and it is written in a faster language. In a real program, always use sorted. In the next lesson, you count the work to see the difference.

Common mistakes

• a = a.sort(). The list becomes None.
• Sorting a list that mixes numbers and text. A TypeError: Python cannot compare 5 with "apple".
• Forgetting that capital letters come first. Use key=str.lower.
• A wrong inner range in bubble sort. An IndexError at i + 1.
• Sorting a copy and forgetting to keep it. sorted(a) on its own line does nothing visible.

Practice

Start with two quick questions. Each New numbers gives you a fresh one, so you can practise as long as you like.

Then the labs and the problems:

1. Warm-up. Open the problem Sort the names and the problem Sort by length.
2. Build. Open the lab Five ways to sort words and the problem The top three scores.
3. Stretch. Open the problem One pass of bubble sort and the problem Selection sort, and write the list after each step.

Remember these

• sorted(x) is a new list. x.sort() changes x and gives back None.
• reverse=True and key= change how the list is sorted. A tuple key sorts by two things.
• Sorting is stable: equal items keep their order.
• Bubble sort swaps neighbours. Selection sort picks the smallest. Python's sorted is faster than both.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

1. What does sorted([3, 1, 2], reverse=True) give?

2. How do you sort words by length?

3. Why does asha come last in sorted(["Meera", "asha", "Kabir"])?

4. After pass 1 of bubble sort on [5, 2, 9, 1], which value is in its place?