Cocktail Shaker Sort
Bidirectional bubble sort that traverses in both directions.
Finds the minimum element and places it at the beginning of the unsorted portion.
Selection Sort is one of the most intuitive sorting algorithms. It divides the array into two regions: a sorted region on the left (initially empty) and an unsorted region on the right (initially the entire array). On each pass, the algorithm finds the minimum element in the unsorted region and swaps it into its correct position at the boundary between the two regions. This process repeats until the unsorted region is empty and the entire array is sorted.
Selection Sort is among the most straightforward sorting algorithms and has been known since the earliest days of computing. Its simplicity made it a natural choice for early computer programs when memory was extremely limited and algorithm efficiency was less understood. While it has long been surpassed by more efficient algorithms for general-purpose sorting, Selection Sort remains a standard example in introductory computer science courses because its logic is easy to follow and its behavior is predictable.
The key insight is that after k passes, the k smallest elements are in their correct final positions at the beginning of the array. Each element is placed exactly once and never moved again.
| Case | Time | Space |
|---|---|---|
| Best | O(n^2) | O(1) |
| Average | O(n^2) | O(1) |
| Worst | O(n^2) | O(1) |
A distinctive characteristic of Selection Sort is that it always performs exactly n(n-1)/2 comparisons, regardless of the initial order of the input. Even on an already-sorted array, it must scan the unsorted region to confirm the minimum. This means Selection Sort is not adaptive -- it cannot exploit existing order in the input. However, it performs at most n-1 swaps, which is the minimum possible for any in-place sorting algorithm. This makes it optimal in terms of data movement.
Compared to Bubble Sort, Selection Sort makes far fewer swaps (O(n) versus O(n^2)) but the same number of comparisons. Compared to Insertion Sort, Selection Sort is strictly worse on nearly-sorted input because it cannot take advantage of existing order. Insertion Sort adapts to the input and achieves O(n) on sorted data, while Selection Sort always takes O(n^2). However, Selection Sort has the advantage of performing a predictable, minimal number of writes to the array -- at most one swap per element.
In its standard implementation, Selection Sort is not a stable sort. Stability means that equal elements maintain their original relative order. Selection Sort can violate this because the swap operation can move an element past other equal elements. For example, consider the array [3a, 3b, 1]. Selection Sort swaps 1 with 3a, producing [1, 3b, 3a], reversing the order of the two 3s. A stable version can be implemented by using shifts instead of swaps (similar to Insertion Sort), but this changes the swap count to O(n^2).
Selection Sort is useful in niche scenarios where the cost of writing data is high but comparisons are cheap -- for example, when sorting data on flash memory or EEPROM, where write operations cause physical wear. Its guaranteed O(n) swaps make it attractive in such contexts. For general-purpose sorting, Insertion Sort is preferred for small arrays and nearly-sorted data, while Merge Sort or Quick Sort should be used for larger datasets.