SelectionSort

Selectionsort, or selection sort, is a simple in-place sorting algorithm. It orders a list by repeatedly selecting the smallest (or largest) element from the unsorted portion and moving it to its final position, expanding the sorted region from the front.

During each pass, the algorithm maintains a boundary between the sorted portion at the front and the unsorted portion at the back. It scans the unsorted portion to find the index of the minimum element, then swaps that element with the first unsorted element.

Time complexity: the number of comparisons is always n(n-1)/2, so the running time is Theta(n^2) in all cases. The number of writes (swaps) is at most n-1, making the algorithm in-place with constant extra space. Best and worst cases share the same asymptotic time.

Stability: standard selection sort is not stable, because elements equal to the chosen minimum may be moved past other equal elements. A stable variant requires more careful handling, such as shifting elements rather than direct swapping.

Algorithm (pseudocode): Procedure selectionSort(A): for i from 0 to length(A)-2: minIndex = i; for j from i+1 to length(A)-1: if A[j] < A[minIndex]: minIndex = j; if minIndex != i: swap A[i] and A[minIndex]