Selection Sort

Overview

Selection sort divides the array into two parts: sorted and unsorted. It repeatedly finds the minimum element from the unsorted part and places it at the beginning of the sorted part. This builds the sorted array one element at a time.

How Selection Sort Works

The algorithm maintains two subarrays: the left part is sorted, and the right part is unsorted. In each iteration, it scans the unsorted portion to find the smallest element and swaps it with the leftmost unsorted element, effectively expanding the sorted region.

The Selection Process

For each position in the array, selection sort finds the minimum value in the remaining unsorted portion. It then swaps that minimum value with the value at the current position. This ensures each position gets its correct element in order.

Time Complexity

Selection sort always requires O(n²) comparisons, regardless of input order, because it must scan the entire unsorted portion to find the minimum each time. It performs fewer swaps than bubble sort but is still quadratic in time complexity.

Advantages

Selection sort is simple to understand and implement. It performs at most n swaps, which is an advantage when swap operations are expensive. It's also in-place, meaning it doesn't require extra memory proportional to the input size.

When to Use

Like bubble sort, selection sort is mainly useful for educational purposes or very small datasets. For larger arrays, more efficient algorithms should be used. It's good for understanding the concept of finding minimums and building sorted arrays incrementally.