Sorting algorithms

Introduction to Sorting Algorithms

Welcome! In this chapter, we are going to look at Sorting Algorithms. Simply put, sorting is the process of putting items into a specific order, such as alphabetical order (A-Z) or numerical order (1-10).

Why do we care? Well, imagine trying to find a name in a phone book if the names weren't in alphabetical order! Computers need to sort data so that they can search through it much faster later on. We are going to focus on the two main methods you need for your AQA exam: the Bubble Sort and the Merge Sort.

1. The Bubble Sort

The Bubble Sort is one of the simplest sorting algorithms to understand. It gets its name because the larger values "bubble up" to the end of the list, just like bubbles rising in a fizzy drink!

How it works (The Mechanics)

The algorithm works by stepping through the list over and over again. Here is the step-by-step process:

1. It looks at the first two items in the list.
2. If they are in the wrong order, it swaps them. If they are in the right order, it leaves them alone.
3. It then moves to the next pair (the 2nd and 3rd items) and repeats the comparison.
4. It continues this until it reaches the end of the list. This is called a pass.
5. The algorithm repeats these passes until it completes a full pass without making any swaps at all. That’s how it knows the list is sorted!

A Real-World Example

Imagine four students standing in a line, and you want to sort them by height (shortest to tallest): [Dave (180cm), Alice (155cm), Chris (170cm), Bob (160cm)].

Pass 1:
- Compare Dave and Alice. Dave is taller, so swap. [Alice, Dave, Chris, Bob]
- Compare Dave and Chris. Dave is taller, so swap. [Alice, Chris, Dave, Bob]
- Compare Dave and Bob. Dave is taller, so swap. [Alice, Chris, Bob, Dave]
Dave has "bubbled" to the end!

Pass 2:
- Compare Alice and Chris. Correct order, no swap.
- Compare Chris and Bob. Chris is taller, so swap. [Alice, Bob, Chris, Dave]
- Compare Chris and Dave. Correct order, no swap.

Pass 3:
- Compare Alice and Bob. Correct order, no swap.
- Compare Bob and Chris. Correct order, no swap.
- Compare Chris and Dave. Correct order, no swap.
No swaps happened in Pass 3, so the list is finished!

Quick Review: Bubble Sort

- Action: Compares adjacent pairs and swaps.
- Stop condition: When a full pass is made with zero swaps.
- Best for: Very small lists or lists that are already almost sorted.

Common Mistake: Students often think the algorithm stops after one pass. Remember, it usually takes multiple passes to get every item into the right place!

Key Takeaway: Bubble sort is easy to understand and write, but it is generally slow for large amounts of data.

2. The Merge Sort

The Merge Sort is a much faster algorithm for large lists. It uses a technique called divide and conquer. Instead of swapping items one by one, it breaks the list down into tiny pieces and then puts them back together in the right order.

How it works (The Mechanics)

Don't worry if this seems a bit more complex at first! It happens in two main stages:

Stage 1: Divide
The algorithm keeps splitting the list in half until every single item is in its own tiny list of one. (A list with only one item is technically already sorted!)

Stage 2: Conquer (Merge)
The algorithm starts merging the tiny lists back together. Every time it merges two lists, it puts the items in the correct order. It keeps doing this until there is only one big, sorted list left.

A Visual Analogy

Think of a messy deck of cards. You split the deck into two piles, then four, then eight, until you are holding individual cards. Then, you take two cards and put them in order. Then you take two pairs and merge them into a sorted group of four, and so on.

Did you know? Merge sort is much more efficient than Bubble sort for huge datasets, like the list of all users on a social media site.

Quick Review: Merge Sort

- Action: Splits the list in half repeatedly, then merges them back in order.
- Technique: Divide and Conquer.
- Best for: Large lists of data.

Key Takeaway: Merge sort is faster than Bubble sort for big lists, but it is more difficult to program and uses more computer memory because it has to create all those sub-lists.

3. Comparing the Algorithms

In your exam, you might be asked why you would choose one algorithm over the other. Here is a simple comparison to help you decide.

Bubble Sort

Advantages:
- It is very simple to write and understand.
- It doesn't use much extra memory (it sorts the list "in place").

Disadvantages:
- It is inefficient (slow) for large lists.

Merge Sort

Advantages:
- It is very efficient (fast) even for massive lists.
- It has a consistent running time regardless of how messy the original list was.

Disadvantages:
- It is more complex to program.
- It uses more memory because it creates many sub-lists during the process.

Memory Aid: Think of Bubble as "Basic" (Simple but slow) and Merge as "Modern" (Complex but fast).

Quick Review: Efficiency

When we talk about "efficiency" in these algorithms, we are usually talking about Time Efficiency—how long it takes the computer to finish the task. As a list gets longer, the time it takes for a Bubble Sort to finish grows much faster than the time it takes for a Merge Sort.

Key Takeaway: For a small list of 5 items, Bubble Sort is fine. For a list of 5 million items, you must use Merge Sort!

Summary Checklist

Can you do the following?

- [ ] Explain how a Bubble Sort uses passes and swaps?
- [ ] Describe the "Divide and Conquer" method used in a Merge Sort?
- [ ] State one advantage of Bubble Sort? (Easy to code/uses less memory)
- [ ] State one advantage of Merge Sort? (Faster for large lists)