Selection sort is one of the simplest sorting algorithms, at any instance it maintains two subarrays in a given array : one with the elements that are already sorted which is built up from left to right starting at front of the array, other with rest of elements in the array that are remaining to be sorted. The algorithm proceeds by finding the smallest element in the unsorted array and swapping it with the left most element of the unsorted array. Following example clarifies this sentence.

Input : 21 9 3 12 6 21 9 3 12 6 3 9 21 12 6 // sorted subarray = {3} 3 6 21 12 9 // sorted subarray = {3,6} 3 6 9 12 21 // sorted subarray = {3,6,9} 3 6 9 12 21 // sorted subarray = {3,6,9,12} output : 3 6 9 12 21

**Complexity Analysis**

You can read about complexities of other sorting algorithms here.

Time complexity :O( N² -- N²-- N² )[Best -- Average -- Worst] Memory :O(1)i.e. just the input array:"in place" Stable : Yes # N being the number of elements in the array

**Usage**

It is inefficient on larger lists due to its O(*N²*) time complexity, and generally performs worse than the similar **insertion sort. **It is easier to implement than most of the other sorting algorithms, can be advantageous over other complicated algorithms, especially when the memory is limited.

**Bottom line: **Simplest algorithm one can implement when time complexity is not concerned.

**Implementation in C**

**Question:** Sort an array of integers in increasing order using selection sort algorithm (format similar to most of the online programming contests )

**Input:**

First line of input contains T, number of test cases

Each test case contains an integer N ≤ 200, the number of integers in that array, followed by N integers separated by N spaces.

**Output:** Sorted array

**Sample Input**

3 5 4 7 9 3 1 3 4 5 5 4 6 10 6 7

**Sample Output**

1 3 4 7 9 4 5 5 6 6 7 10

**Code**

Brief explanation is given in the gist.