Selection Sort and its Implementation in ‘C’

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() 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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s