Master Python Sorting: Bubble & Selection Sort Explained and Optimized

Sorting Concepts

Internal sorting processes data stored entirely in memory, while external sorting accesses external storage. Internal sorting is the foundation and can be classified by principle (insertion, exchange, selection, merge) or by complexity (simple vs advanced). Simple sorts include bubble sort, simple selection sort, and direct insertion sort.

Algorithm evaluation criteria are computational effort (number of comparisons and moves) and additional storage required.

Simple Sort: Bubble Sort Python Implementation and Optimization

Basic implementation follows the classic bubble sort algorithm, repeatedly swapping adjacent out‑of‑order elements.

Basic Implementation

Optimized Implementation

Introduce a flag that records whether any swap occurred during a pass; if no swaps happen, the list is already sorted and the algorithm can terminate early.

Summary

Bubble sort repeatedly compares adjacent elements. The optimization with a swap‑flag can end the algorithm early when a pass makes no exchanges. Worst‑case complexity is O(n²) with n(n‑1)/2 comparisons; best case (already sorted) requires only n‑1 passes.

Simple Sort: Selection Sort Python Implementation and Optimization

The core of selection sort is to find the extreme (minimum or maximum) value in each pass and place it at the appropriate end, repeating until the list is sorted.

Basic Implementation

Optimized Implementation – Binary Selection Sort

Each pass selects both the maximum and minimum values, reducing the number of iterations by half.

Equal‑Value Optimization

If the maximum and minimum found in a pass are equal, the remaining elements are identical and the algorithm can terminate early.

Advanced Equal‑Value Optimization

Example: [1,1,1,1,1,1,1,1,2]; the minimum index is -2 and maximum index 8, causing unnecessary swaps of identical values. Adding a check avoids these redundant operations.

Summary

Selection sort also requires multiple passes, discovering an extreme each round. It cannot know early if the list is sorted, but it can detect when extremes are already in place. Comparisons total n(n‑1)/2, time complexity O(n²). Fewer swaps than bubble sort make it slightly more efficient.