Sorting a list

Why order matters

Sorting means putting the items of a list into a defined order, smallest to largest for numbers, A to Z for words. It sounds like a chore, but it is one of the most useful things you can do to data, because order unlocks speed. A sorted list of names is far quicker to search, a sorted list of scores makes the top and bottom obvious, and merging two sorted lists is easy while merging two jumbled ones is not.

Because sorting is so common, it is worth understanding one method from the inside before handing the job to Python. Seeing how a sort actually moves items around takes the mystery out of the built-in tool and, just as importantly, shows you why the built-in tool is the one to use.

A simple sort, step by step

Here is one of the easiest sorts to picture, often called selection sort. The idea is plain: find the smallest item, put it at the front, then repeat on the rest of the list.

Take a short list of exam scores, [70, 45, 88, 60].

• Look at the whole list and find the smallest, 45. Swap it to the front: [45, 70, 88, 60].
• Ignore the 45 now. Look at the rest and find the smallest, 60. Swap it into second place: [45, 60, 88, 70].
• Ignore the first two. The smallest of what is left is 70. Swap it into third place: [45, 60, 70, 88].
• One item remains, so it is already where it belongs. Done.

In code the two "look" steps become a loop inside a loop.

def selection_sort(scores):
    numbers = list(scores)          # work on a copy, leave the original alone
    for start in range(len(numbers)):
        smallest = start
        for i in range(start + 1, len(numbers)):
            if numbers[i] < numbers[smallest]:
                smallest = i
        numbers[start], numbers[smallest] = numbers[smallest], numbers[start]
    return numbers

print(selection_sort([70, 45, 88, 60]))   # [45, 60, 70, 88]

The outer loop picks each position in turn; the inner loop hunts for the smallest remaining value to drop into that position. That nesting is the tell you met with Big-O: a loop inside a loop over the data.

Let Python do it: sorted()

You will almost never write that by hand in real work, because Python already sorts for you. The built-in sorted function takes any list and returns a new sorted one, and reverse=True flips the order.

scores = [70, 45, 88, 60]

print(sorted(scores))                 # [45, 60, 70, 88]
print(sorted(scores, reverse=True))   # [88, 70, 60, 45]
print(scores)                         # [70, 45, 88, 60], untouched

It also sorts words alphabetically, and with the key option it can sort by whatever you choose, such as the length of each word. sorted returns a fresh list; the list method scores.sort() does the same job but rearranges the original in place.

What sorting costs

Now reason about the cost, which is the whole point of putting these side by side. Selection sort has a loop inside a loop, so its work grows as O(n²): double the list and the work roughly quadruples. Python's built-in sort uses a much cleverer algorithm and grows as O(n log n), which is dramatically gentler.

The lesson is the same one Big-O keeps teaching. Writing the sort yourself is worth it once, to see the machinery. After that, the tool the language gives you is both simpler and faster, and choosing it is not laziness, it is good judgement about how the work scales.

Put the whole module to work

You have three lessons of reasoning behind you: how growth shapes differ, how to compare two working approaches, and what sorting costs. The practice below is the one place in this module where you commit to a choice yourself and then defend it when the job changes under you.

Your reasoning stays in this browser. Nothing is uploaded, graded or kept.

Module practice · 15 to 20 min

Choose an approach, then defend it when the job changes

You have read how growth shapes differ. This is where you commit to one. Your work stays in this browser: nothing is uploaded, graded or kept.

The activity controls are getting ready. You can read this section now; choices will become available when the page is ready.

1 · Choose, for the job as it stands

A community event has a guest list of about 200 names. People arrive at the door one at a time, roughly 200 arrivals over the evening. For each arrival you need a quick yes or no: are they on the list?

Which approach would you write?

Keep the guest list as a list and check each arrival with `in`if person in guests:Build a set from the guest list first, then check each arrival against the setguest_set = set(guests)

In one line, why? Name what you are optimising for.Commit this choice

If your reasoning stalls, count the loops

Take the code in front of you and count only the loops that run over the data. No loop is usually O(1). One loop is usually O(n). A loop inside a loop is usually O(n squared).

The catch is that some loops are hidden. person in guests looks like one step on one line, but on a list it is a loop: Python walks the names until it finds a match. Put that hidden loop inside your own loop over the arrivals and you have a loop inside a loop.

So ask of each line: does this line, by itself, touch every item? If yes, it is a loop even when it does not look like one.

If that was straightforward

When would you deliberately choose the slower shape? The honest answer is: more often than a Big-O table suggests.

Building the set costs a pass over the data and real memory. If the guest list is twelve names, or the check runs once and never again, the scan is simpler to read and the difference is unmeasurable. Simplicity is a real engineering value, not a consolation prize.

Big-O also hides constants. An O(n) approach with an expensive step can lose to an O(n squared) one with a cheap step, right up until n gets large. The notation tells you which one wins eventually, not which one wins today.

Your turn: describe one situation from your own work or study where you would keep the simpler, slower version on purpose, and what you would watch for that would change your mind.

Reset this practiceThis device remembers only which stage you reached and which options you picked.

Found something unclear, outdated or improvable? Suggest an improvement

Check yourself

1. Walk through selection sort on the list [3, 1, 2] in words. Which item moves to the front first, and what does the list look like after each pass?
2. Selection sort is O(n²) and Python's sorted is O(n log n). On a list that suddenly grows from 100 to 1,000 items, why does that difference in shape matter so much more than at 100?
3. sorted(scores) returns a new list while scores.sort() changes the original. Describe a situation where you would specifically want to keep the original list unchanged.