Sorting for Beginners: Understanding Bubble Sort and Selection Sort

Learning to code involves understanding fundamental concepts, and one of the most important is how to organize data efficiently. This is where sorting algorithms come into play. Sorting is the process of arranging elements in a list or array into a specific order (ascending or descending). While there are many complex and highly efficient sorting methods out there, starting with the basics is key. This article, focusing on Bubble Sort and Selection Sort Explained, will introduce you to two of the simplest sorting algorithms, perfect for beginners.

Understanding how these algorithms work provides a foundational insight into computational thinking, comparison operations, and efficiency. Even though they aren’t typically used for sorting massive datasets in real-world applications due to their performance limitations, their simplicity makes them excellent teaching tools.

What is Bubble Sort?

Bubble Sort is often the first sorting algorithm taught because of its straightforward logic. It’s a comparison-based algorithm, meaning it sorts by comparing adjacent elements.

The core idea is simple: repeatedly step through the list, compare adjacent elements, and swap them if they are in the wrong order. This process is repeated multiple times, in passes, until the list is sorted.

Think of it like bubbles in water – the larger (or smaller, depending on the sorting order) elements gradually “bubble up” to their correct position in the list with each pass.

Here’s how it works in steps:

1. Start at the beginning of the list.
2. Compare the first two elements. If they are in the wrong order (e.g., the first is larger than the second for ascending sort), swap them.
3. Move to the next pair of elements (the second and third), compare them, and swap if necessary.
4. Continue this process for the entire list. After the first pass, the largest element will be at the end of the list.
5. Repeat the process for the remaining unsorted part of the list. In each subsequent pass, the comparison range shrinks as elements are placed in their final sorted positions.
6. The algorithm stops when a complete pass through the list results in no swaps, indicating that the list is sorted.

Let’s visualize a tiny example sorting `[5, 1, 4, 2, 8]` ascending:

First Pass:

• (5, 1) -> swap -> [1, 5, 4, 2, 8]
• (5, 4) -> swap -> [1, 4, 5, 2, 8]
• (5, 2) -> swap -> [1, 4, 2, 5, 8]
• (5, 8) -> no swap -> [1, 4, 2, 5, 8]. At the end of the first pass, 8 is in its final place.

Second Pass (range shrinks):

• (1, 4) -> no swap -> [1, 4, 2, 5, 8]
• (4, 2) -> swap -> [1, 2, 4, 5, 8]
• (4, 5) -> no swap -> [1, 2, 4, 5, 8]. At the end of the second pass, 5 is in its final place.

Third Pass (range shrinks further):

• (1, 2) -> no swap -> [1, 2, 4, 5, 8]
• (2, 4) -> no swap -> [1, 2, 4, 5, 8]. At the end of this pass, the list is sorted.

Fourth Pass (check for swaps):

• (1, 2) -> no swap -> [1, 2, 4, 5, 8]
• (2, 4) -> no swap -> [1, 2, 4, 5, 8]
• (4, 5) -> no swap -> [1, 2, 4, 5, 8]. No swaps occurred, the algorithm terminates.

[Hint: Insert image/video visualization of Bubble Sort here]

Bubble Sort’s Efficiency (or Lack Thereof)

Bubble Sort is simple, but it’s not efficient for large lists. Its time complexity is O(n²), which means the time it takes to sort increases quadratically with the number of elements (n). If you double the number of items, the sorting time increases by roughly four times. This is why you won’t find Bubble Sort in high-performance sorting libraries, but it’s great for learning the concept of sorting.

What is Selection Sort?

Selection Sort is another simple, comparison-based sorting algorithm often introduced alongside Bubble Sort. Like Bubble Sort, it has a time complexity of O(n²) and is generally considered inefficient for large datasets. However, it has a slight advantage in certain scenarios, particularly when memory writes (swaps) are significantly more expensive than reads (comparisons), as it performs a minimal number of swaps.

Selection Sort works by dividing the list into two portions: a sorted sublist built from the left and an unsorted sublist taking up the rest. The algorithm repeatedly finds the minimum element from the unsorted sublist and swaps it with the first element of the unsorted sublist. The boundary between the sorted and unsorted portions shifts one element to the right with each step.

Here’s the process:

1. Start with the entire list as the unsorted sublist, and an empty sorted sublist.
2. Iterate through the unsorted sublist to find the minimum element.
3. Swap the found minimum element with the first element of the unsorted sublist. This element is now considered part of the sorted sublist.
4. Move the boundary between the sorted and unsorted sublists one position to the right.
5. Repeat steps 2-4 until the unsorted sublist is empty, at which point the entire list is sorted.

Let’s use the example `[64, 25, 12, 22, 11]` sorting ascending:

Initial list: [64, 25, 12, 22, 11]

• Pass 1: Unsorted part is [64, 25, 12, 22, 11]. Find minimum: 11. Swap 11 with the first element (64). List becomes [11, 25, 12, 22, 64]. Sorted part: [11].
• Pass 2: Unsorted part is [25, 12, 22, 64]. Find minimum: 12. Swap 12 with the first element of the unsorted part (25). List becomes [11, 12, 22, 64, 25] -> Correction from original wiki example, the swap is with the first element of the unsorted part, which is 25. So list becomes [11, 12, 22, 64, 25]. Wait, re-reading the wiki example: “swapping (exchanging) it with the leftmost unsorted element”. My bad, the example was: `11 25 12 22 64` after the first step. This suggests the swap was with the original first element, 64. The next step in the wiki example is `11 12 25 22 64`. This means the minimum in `[25, 12, 22, 64]` which is 12 was swapped with 25. The wiki example seems to imply the swap happens in place at the correct position, not always the first element of the diminishing unsorted list. Let’s follow the description “exchanging (swapping) it with the leftmost unsorted element”.

Let’s redo the example following the standard description of Selection Sort:

Initial list: [64, 25, 12, 22, 11]

• Pass 1: Unsorted part is `[64, 25, 12, 22, 11]`. Smallest element is 11. Swap 11 with the first element of the unsorted part (64). List becomes `[11, 25, 12, 22, 64]`. Sorted part: `[11]`.
• Pass 2: Unsorted part is `[25, 12, 22, 64]`. Smallest element is 12. Swap 12 with the first element of the unsorted part (25). List becomes `[11, 12, 25, 22, 64]`. Sorted part: `[11, 12]`.
• Pass 3: Unsorted part is `[25, 22, 64]`. Smallest element is 22. Swap 22 with the first element of the unsorted part (25). List becomes `[11, 12, 22, 25, 64]`. Sorted part: `[11, 12, 22]`.
• Pass 4: Unsorted part is `[25, 64]`. Smallest element is 25. Swap 25 with the first element of the unsorted part (25). List remains `[11, 12, 22, 25, 64]`. Sorted part: `[11, 12, 22, 25]`.
• Pass 5: Unsorted part is `[64]`. Smallest element is 64. Swap 64 with the first element of the unsorted part (64). List remains `[11, 12, 22, 25, 64]`. Sorted part: `[11, 12, 22, 25, 64]`. The list is sorted.

[Hint: Insert image/video visualization of Selection Sort here]

Selection Sort’s Complexity

Like Bubble Sort, Selection Sort has a time complexity of O(n²). This is because, for a list of n elements, it requires n-1 passes. In the first pass, it scans n elements to find the minimum. In the second pass, it scans n-1 elements, and so on, down to scanning 1 element in the last pass. The total number of comparisons is (n-1) + (n-2) + … + 1, which sums to n(n-1)/2, a quantity proportional to n². The number of swaps is exactly n-1 (or n if we consider the final element placement), which is significantly fewer than Bubble Sort in the worst case.

Why Learn Bubble Sort and Selection Sort?

Given their O(n²) complexity, you might wonder why bother learning Bubble Sort and Selection Sort when faster algorithms like Merge Sort or Quick Sort (which often have O(n log n) complexity) exist. The reason is their simplicity. They are easy to understand and implement, making them excellent starting points for grasping core sorting concepts:

• Comparison: Understanding how elements are compared.
• Swapping: Learning how to exchange element positions.
• Iteration and Passes: Seeing how repeated passes refine the list’s order.
• Time Complexity: Getting a tangible feel for what O(n²) looks like in practice compared to the size of the input.
• Foundation: These simple algorithms provide a mental model that helps in understanding more complex sorting techniques later.

For extremely small lists, the overhead of more complex algorithms might even make these simpler ones competitive, though this is a niche use case.

Understanding how data is structured and manipulated is crucial in programming. Articles like Data Structures Explained Simply (Arrays, Lists, Stacks, Queues) can provide valuable context on the types of data collections these algorithms operate on.

To delve deeper into how we measure algorithm efficiency, explore resources on Big O Notation.

Conclusion

Bubble Sort and Selection Sort are foundational sorting algorithms for beginners. They introduce the core ideas of comparison, swapping, and iterative refinement in sorting, despite their inefficiency for large datasets due to their O(n²) time complexity. By understanding these simple methods, you build a strong basis for tackling more advanced sorting algorithms and appreciate the importance of algorithmic efficiency in computer science.