Selection sort is a simple sorting algorithm that works by repeatedly finding the minimum element from the unsorted portion and placing it at the beginning. The algorithm divides the array into sorted and unsorted regions. It has O(n²) time complexity but uses only O(1) additional space, making it an in-place sorting algorithm.
Let's walk through selection sort step by step using the array [64, 25, 12, 22, 11]. In the first iteration, we start with index 0 as our minimum. We compare 64 with each subsequent element: 25, 12, 22, and 11. We find 11 is the smallest, so we swap it with 64. Now 11 is in its correct position. We repeat this process for the remaining unsorted portion until the entire array is sorted.
Here's the complete C++ implementation of selection sort. The function takes an array and its size as parameters. The outer loop iterates through each position, while the inner loop finds the minimum element in the remaining unsorted portion. We use the swap function to exchange elements. The main function demonstrates how to call the selection sort function with a sample array.
Selection sort has a time complexity of O(n²) because it uses nested loops. The outer loop runs n-1 times, and for each iteration, the inner loop performs decreasing comparisons. This gives us (n-1) + (n-2) + ... + 1 comparisons, which equals n(n-1)/2, resulting in O(n²). The space complexity is O(1) since it sorts in-place using only constant extra memory. This quadratic growth makes selection sort inefficient for large datasets compared to algorithms like merge sort or quick sort.
Let's see selection sort in action with practical examples. For the integer array [29, 10, 14, 37, 13], we find 10 as the minimum and swap it to the first position, then continue until we get [10, 13, 14, 29, 37]. Similarly, for characters ['d', 'a', 'c', 'b'], we sort alphabetically to get ['a', 'b', 'c', 'd']. Selection sort is ideal for small datasets, memory-constrained environments, and when you need a simple, predictable algorithm.