#### Apr 21, 2021

# Selection Sort

Selection sort is anin-place comparison sorting algorithm. Selection sort is among the simplest of sorting techniques and it work very well for small data. Selection sort has a quite important application because each item is actually moved at most once, Selection sort is a method of choice for sorting files with very large records and small keys.

The Selection sort spends most of its time trying to find the minimum element in the unsorted part of the array. It has O(n^{2}) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. The worst case occurs if the array is already sorted in descending order.

It has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited. The algorithm divides the input list into two parts - the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list.

for i = 1 to n-1 do
min j = i;
min x = A[i]
for j = i + 1 to n do
If A[j] < min x then
min j = j
min x = A[j]
A[min j] = A [i]
A[i] = min x