Bubble Sort vs Selection Sort
Two of the simplest O(n²) sorting algorithms, often taught side by side as a first introduction to sorting — but they behave quite differently on real data.
A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.
When to use it
Use Bubble Sort mainly for teaching, or when the input is nearly sorted — with an early-exit optimization it can finish in close to O(n) on already-sorted data.
An in-place comparison sorting algorithm. It divides the input list into two parts: a sorted sublist which is built up from left to right and a sublist of the remaining unsorted items that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.
When to use it
Use Selection Sort when the cost of swapping elements is high (e.g. large records) since it performs at most n swaps, compared to Bubble Sort's potentially O(n²) swaps.
Key Differences
- Bubble Sort repeatedly swaps adjacent out-of-order elements; Selection Sort finds the minimum remaining element and swaps it into place once per pass.
- Bubble Sort can be optimized to exit early on a sorted/nearly-sorted array; Selection Sort always runs a full O(n²) comparison scan regardless of input order.
- Selection Sort performs O(n) swaps total; Bubble Sort can perform up to O(n²) swaps.
- Both are stable in typical implementations, both sort in-place with O(1) extra space.
Neither scales to large datasets. Selection Sort is preferable when writes/swaps are expensive; Bubble Sort is preferable only for its simplicity or near-sorted inputs.