Introduction to Sorting Algorithms
Welcome to your study notes on Sorting Algorithms! Have you ever searched for a high score in a video game, scrolled through contacts on a phone, or organized a hand of playing cards from lowest to highest? All of these rely on sorting.
In Computer Science, computers handle huge amounts of data. To make that data easy to search, read, and manage, we use step-by-step procedures called algorithms to arrange items into a specific order (such as ascending numerical order from smallest to largest, or alphabetical order from A to Z).
Don't worry if this seems tricky at first! We will break down how each algorithm works step-by-step using clear examples and everyday analogies.
Key Takeaway: A sorting algorithm is a set of step-by-step instructions that takes an unsorted list of items and rearranges them into order (such as ascending numerical or alphabetical order).
Computational Thinking and Sorting
Sorting algorithms are a great way to see computational thinking in action:
• Abstraction: Focusing on the key details (comparing two numbers and swapping them) while ignoring unnecessary information (like what colour the numbers are written in).
• Decomposition: Breaking down the big problem of sorting an entire list into smaller, manageable steps—such as comparing one pair of items at a time or splitting a list into halves.
• Algorithmic Thinking & Logical Reasoning: Creating and following clear rules step-by-step, and comparing different algorithms to see which one works best for a specific job.
Understanding the "Swap" Logic
Many sorting algorithms work by swapping two values in a list. But how does a computer swap two values without losing data?
Imagine you have a glass of orange juice (Glass \(A\)) and a glass of apple juice (Glass \(B\)). If you pour Glass \(B\) directly into Glass \(A\), the drinks get mixed together and you lose the orange juice! To swap them safely, you need a temporary third glass (Glass \(temp\)):
1. Pour Glass \(A\) into Glass \(temp\) (\(temp = A\))
2. Pour Glass \(B\) into Glass \(A\) (\(A = B\))
3. Pour Glass \(temp\) into Glass \(B\) (\(B = temp\))
In computer programming, this temporary variable ensures that no data is overwritten or lost during a swap.
Algorithm 1: Bubble Sort
Bubble Sort is one of the simplest sorting algorithms. It works by repeatedly stepping through a list, comparing pairs of adjacent (side-by-side) items, and swapping them if they are in the wrong order.
How Bubble Sort Works:
1. Start at the very beginning of the list.
2. Compare the first two adjacent items (Item \(1\) and Item \(2\)).
3. If they are in the wrong order (e.g., the first is bigger than the second in an ascending sort), swap them. If they are already in order, leave them as they are.
4. Move to the next pair (Item \(2\) and Item \(3\)) and repeat the comparison and swap.
5. Continue stepping through the list until you reach the end. This is called completing one pass. By the end of Pass \(1\), the largest number has "bubbled up" to its correct position at the end of the list.
6. Repeat the passes until a full pass is completed with zero swaps. Zero swaps means the list is completely sorted!
Step-by-Step Example (Tracing Bubble Sort):
Let's sort the list: [5, 1, 4, 2] in ascending order.
Pass 1:
• Compare 5 and 1: \(5 > 1\), so swap \(\implies\) [1, 5, 4, 2]
• Compare 5 and 4: \(5 > 4\), so swap \(\implies\) [1, 4, 5, 2]
• Compare 5 and 2: \(5 > 2\), so swap \(\implies\) [1, 4, 2, 5]
End of Pass 1 state: [1, 4, 2, 5] (The largest number, 5, is now in its final position. Swaps were made, so we must do another pass!)
Pass 2:
• Compare 1 and 4: in order, no swap \(\implies\) [1, 4, 2, 5]
• Compare 4 and 2: \(4 > 2\), so swap \(\implies\) [1, 2, 4, 5]
• Compare 4 and 5: in order, no swap \(\implies\) [1, 2, 4, 5]
End of Pass 2 state: [1, 2, 4, 5] (Swaps were made, so we must check again!)
Pass 3:
• Compare 1 and 2: in order, no swap
• Compare 2 and 4: in order, no swap
• Compare 4 and 5: in order, no swap
End of Pass 3: 0 swaps occurred! The algorithm now knows the list is fully sorted.
Key Takeaway: Bubble Sort compares adjacent pairs and repeats passes until a complete pass occurs with zero swaps. It is simple to program, but becomes slow and inefficient on large lists.
Algorithm 2: Insertion Sort
Insertion Sort works the same way many people sort a hand of playing cards. It builds a sorted list one item at a time by taking an unsorted item and inserting it into its correct position.
How Insertion Sort Works:
1. Conceptually split the list into two parts: a sorted partition on the left and an unsorted partition on the right.
2. At the start, the first single item is considered sorted on its own.
3. Look at the first item in the unsorted partition.
4. Compare it backwards against the items in the sorted partition.
5. Shift any larger items one position to the right to make space.
6. Insert the item into its correct sorted spot.
7. Repeat this process until there are no unsorted items left.
Step-by-Step Example (Tracing Insertion Sort):
Let's sort the list: [6, 3, 7, 2] in ascending order.
• Start: Sorted part is [6] | Unsorted part is [3, 7, 2]
• Step 1: Take 3. Compare with 6. Since \(3 < 6\), shift 6 to the right and insert 3.
Current state: [3, 6 | 7, 2]
• Step 2: Take 7. Compare with 6. Since \(7 > 6\), it is already in the right place.
Current state: [3, 6, 7 | 2]
• Step 3: Take 2. Compare backwards: \(2 < 7\) (shift 7), \(2 < 6\) (shift 6), \(2 < 3\) (shift 3). Insert 2 at the beginning.
Final sorted state: [2, 3, 6, 7]
Key Takeaway: Insertion Sort repeatedly takes the next item from the unsorted section and inserts it into its correct place in the sorted section by shifting larger elements. It is very efficient for small lists or lists that are already mostly sorted.
Algorithm 3: Merge Sort
Merge Sort is a powerful algorithm that uses an approach called Divide and Conquer. Instead of sorting the whole list all at once, it breaks the list down into tiny pieces, sorts the pieces, and combines them back together.
How Merge Sort Works:
Merge Sort operates in two main stages:
1. Divide: Repeatedly split the unsorted list in half until every sub-list contains exactly one element. (A list with only one single item is already sorted by definition!).
2. Conquer / Combine (Merge): Repeatedly merge adjacent pairs of sub-lists back together in sorted order. To merge two sub-lists, compare their front items, place the smaller one into a new combined list, and repeat until all items are combined into one fully sorted list.
Step-by-Step Example (Tracing Merge Sort):
Let's sort the list: [8, 3, 5, 1]
Stage 1: Divide (Splitting)
• Split [8, 3, 5, 1] into two halves: [8, 3] and [5, 1]
• Split again into individual lists: [8] and [3], [5] and [1]
Stage 2: Combine (Merging in Order)
• Merge [8] and [3]: Compare 8 and 3 \(\implies\) [3, 8]
• Merge [5] and [1]: Compare 5 and 1 \(\implies\) [1, 5]
• Merge [3, 8] and [1, 5]:
- Compare front items 3 and 1: 1 is smaller \(\implies\) take 1
- Compare front items 3 and 5: 3 is smaller \(\implies\) take 3
- Compare front items 8 and 5: 5 is smaller \(\implies\) take 5
- Take the remaining 8 \(\implies\) take 8
Final sorted list: [1, 3, 5, 8]
Key Takeaway: Merge Sort divides lists down until they have a size of \(1\), then merges them back together in order. It is much faster on large datasets than Bubble Sort or Insertion Sort, but it requires extra memory to store the sub-lists.
Comparing Algorithm Utility
Under the statutory curriculum, you need to use logical reasoning to compare how useful different algorithms are for a given situation. Here is how they compare:
1. Bubble Sort:
• How it works: Compares adjacent pairs across multiple passes.
• Best use case: Small lists, or checking if a list is already sorted.
• Main limitation: Very slow and inefficient for large amounts of data.
2. Insertion Sort:
• How it works: Inserts items into a growing sorted partition.
• Best use case: Small datasets, or adding new items into an already sorted list.
• Main limitation: Inefficient for large, reverse-ordered, or heavily scrambled lists.
3. Merge Sort:
• How it works: Divide and conquer (splits lists, then merges them in order).
• Best use case: Large datasets where consistent, fast speed is essential.
• Main limitation: Requires extra computer memory to store all the divided sub-lists during the merge process.
Common Pitfalls and Mistakes to Avoid
• Stopping Bubble Sort too early: Remember that you cannot stop just because you reached the end of the list. You must complete a full pass with zero swaps before you can prove the list is sorted.
• Thinking division sorts in Merge Sort: Splitting the list in half does not sort the numbers. The actual sorting only happens during the merging stage when values are compared and joined.
• Confusing Shifting with Swapping: Insertion Sort shifts existing sorted items to the right to make an empty spot for insertion; it does not simply swap adjacent pairs across the entire list like Bubble Sort.
• Assuming Merge Sort is always the only choice: While Merge Sort is great for large datasets, for very small lists or lists that are already mostly sorted, simple algorithms like Insertion Sort can be easier and use less working memory.
Quick Review Summary
• Bubble Sort: Compare side-by-side pairs \(\implies\) Swap if out of order \(\implies\) Stop when a full pass has 0 swaps.
• Insertion Sort: Split into sorted and unsorted sections \(\implies\) Pick next unsorted item \(\implies\) Shift larger items \(\implies\) Insert into place.
• Merge Sort: Divide repeatedly into lists of size 1 \(\implies\) Merge sub-lists back together in sorted order.