Selection Sort

Selection sort is ideally the simplest sorting algorithm. This is a comparison based sorting, the list is divided into two parts, the smallest element is selected from the unsorted array and is put at the first position. Now, this first element becomes part of the sorted array. This process continues until all the elements of the array are sorted.


Drawback: the algorithm is not suitable for large datasets as its worst-case complexity is O (n^2).


Working:

Lets assume the array given below is the one to be sorted.

Selection Sort Example

Taking the first element of the array, we will compare every element of the array with it, whenever we get a smaller element, we swap them. In this case, 9 will be smaller than 13.

selection sort example

When we swap 9 and 13, the resultant array will be:

selection sort example

Now, we checked that 13 is the second lowest element in the array. So we check the elements with it and swap positions.

Selection Sort example

after the iteration

selection sort example

In a similar manner, we find the next lower element of the array which is 18 and swap the positions to place 18 on the right place.

selection sort example

After swapping, the resultant array will be:

selection sort example

Finding the next lowest element, we came at 26

selection sort example

So we need to swap 26 with 32. Resultant array after this iteration:

selection sort example

Similarly, the next lowest element is 32 which needs to be swapped with 34, the array will be:

selection sort example

The array is in the sorted position now. So, the final sorted array is:

selection sort examples

 

Algorithm

Let's check out how the sorting algorithm works,

Step-1: set minimum location to 0.


Step-2: search for the lowest valued element in the list.


Step-3: swap it with the element at the minimum position.


Step-4: increment min. to point to the next element.


Step-5: Repeat until the array is sorted.