Selection sort | Iterative & Recursive

Given an array of integers, sort it using selection sort algorithm.


Selection sort is a unstable, in-place sorting algorithm known for its simplicity, and it has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited. It can be implemented as a stable sort. It has O(n2) time complexity, making it inefficient to use on large lists. Among simple average-case O(n2) algorithms, selection sort almost always outperforms bubble sort and generally performs worse than the similar insertion sort.

The biggest advantage of using selection sort is that we only requires maximum n swaps (memory write) where n is the length of the input. insertion sort, on the other hand, takes O(n2) number of writes. This can be very important if memory write operation is significantly more expensive than memory read operation, such as with Flash memory, where every write lessens the lifespan of the memory.

How it works?

The idea is to divide the array into two subsets – sorted sublist and unsorted sublist. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, swapping it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right. Below example explains it all –

            3  5  8  4  1  9 -2
i = 0      -2  5  8  4  1  9  3
i = 1      -2  1  8  4  5  9  3
i = 2      -2  1  3  4  5  9  8
i = 3      -2  1  3  4  5  9  8
i = 4      -2  1  3  4  5  9  8
i = 5      -2  1  3  4  5  8  9

 
Iterative C++ implementation –
 

Download   Run Code

Output:

-2 1 3 4 5 8 9

 
Recursive C++ implementation –
 

Download   Run Code

Output:

-2 1 3 4 5 8 9

Both worst and best case time complexity of selection sort is O(n2).
Auxiliary space used by it is O(1).

 
References:
https://en.wikipedia.org/wiki/Selection_sort

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂