Sorting algorithms

Introduction

Sorting puts items in order, and it is one of the most studied problems in computer science. Python's sorted() does it for you, but writing two simple sorting algorithms yourself, and watching them run, teaches how algorithms compare and move data.

Sorted data makes almost everything easier, from searching to spotting duplicates, which is why sorting is among the most studied problems in computer science. Watching simple algorithms move values builds intuition for how all algorithms are compared.

How it works

Selection sort

nums = [29, 10, 14, 37, 13]
for i in range(len(nums)):
    smallest = i
    for j in range(i + 1, len(nums)):
        if nums[j] < nums[smallest]:
            smallest = j
    nums[i], nums[smallest] = nums[smallest], nums[i]
print(nums)

Selection sort finds the smallest remaining value and swaps it into the next position. Watch smallest in the variables panel: each pass it starts at i, then jumps whenever a smaller value turns up, such as nums[j] < nums[smallest] → 10 < 29 → True. It is also O(n²), but it does at most one swap per pass.

Sorting in real programs

students = [("Rahim", 3.4), ("Nadia", 3.9), ("Karim", 3.6)]
by_cgpa = sorted(students, key=lambda s: s[1], reverse=True)
print(by_cgpa[0])
names = sorted(name for name, cgpa in students)
print(names)

In real code, use sorted() (which returns a new list) or list.sort() (which sorts in place). Both are fast, O(n log n), and can sort by anything:

• key=lambda s: s[1] sorts each student by the second item, the CGPA. A lambda is a tiny unnamed function; step into sorted and you will see a <lambda> frame for each student.
• reverse=True sorts from largest to smallest.

Syntax

sorted(nums)                      # a new list
nums.sort()                       # in place
sorted(words, key=len)
sorted(pairs, key=lambda p: p[1], reverse=True)

Example

nums = [5, 2, 4, 1]
n = len(nums)
for i in range(n - 1):
    for j in range(n - 1 - i):
        if nums[j] > nums[j + 1]:
            nums[j], nums[j + 1] = nums[j + 1], nums[j]
print(nums)

Bubble sort walks through the list comparing neighbours, and swaps any pair that is in the wrong order. After the first pass, the largest value has "bubbled" to the end; each further pass needs to go one step less far.

Step through and watch the list in the objects panel. The calculation box shows every comparison, such as nums[j] > nums[j + 1] → 5 > 2 → True, and the line after it swaps the pair. For n items it makes about n × n / 2 comparisons: O(n²).

Line by line

1. nums is the list, and n is its length.
2. The outer loop makes n - 1 passes.
3. The inner loop compares each pair of neighbours, stopping earlier on each pass.
4. A pair in the wrong order is swapped in one line.
5. After the last pass, the whole list is in order.

Expected result

[1, 2, 4, 5]

In the real world

Sorted results, ranked search listings and leaderboards are everywhere. Python's own sorted uses an algorithm called Timsort, which also takes advantage of any order that is already in the data.

Common mistakes

• result = nums.sort() sets result to None: sort() changes the list in place. Use sorted(nums) to get a new list.
• An off-by-one inner loop in bubble sort: nums[j + 1] must stay inside the list, so j stops at n - 2 - i.
• Sorting a mix of numbers and text raises a TypeError; Python cannot compare 3 with "a".

Best practices

• Use sorted or list.sort unless you are learning how sorting works.
• Use key rather than comparing by hand.
• Sort a copy if the original order still matters.

Summary

Bubble and selection sort are simple O(n²) algorithms that show how sorting works. Python's sorted is O(n log n) and sorts by anything using key. list.sort() works in place and returns None.

Practice

Write insertion sort: take each item in turn and move it left until the item before it is not larger. Visualize it on [4, 3, 2, 10, 12, 1] and count the comparisons.

Mark lesson complete