Selection Sort

Suppose we are given a lot of numbers, and then we are asked to sort them using a selection sort algorithm, and then the group after sorting will look like this.

we would have (n-1) + (n-2) + (n-3) + (n-4) + . . . . . + 1 comparisons.

Sum from 1 to n-1, we get , and hence the time complexity of the algorithm would be O(n2).

Selection sort algorithm is not a stable algorithm.

selection sort is not an adaptive algorithm.

This algorithm offers the benefit of making the least number of swaps to sort an array.

Code :

arr = [9, 1, 8, 2, 4]

for i in range(len(arr)):

    min = i

    for j in range(i + 1, len(arr)):

        if arr[min] > arr[j]:

            min = j

    arr[i], arr[min] = arr[min], arr[i]

   

print("Sorted array")

for i in range(len(arr)):

    print("%d" % arr[i])

Output :

Sorted array

1

2

4

8

9

Explanation :

In the selection sort, we have to select the smallest element in the array and put it in the right index.

Let the first element be the smallest element and create a 'min' variable which will store the index of smallest element. Now you have to compare smallest element with all other elements in the Array, this can be done by using nested for loop. If the value less than smallest value is found then update the 'min' variable with the index of new smallest value. After comparing all the element you will get the actual smallest number in the array and sorted array increases by 1 and unsorted array decreases by 1. Now you have to swap the value at 'min' index with the value at 'i' index.

This is the first pass and all the other pass will work like this. Unsorted and sorted will keep decreasing and increasing respectively.

Let there are n elements in the array, then number of pass will be (n-1).

minimum swap will be zero and maximum swap will be (n-1).

Here we have taken 5 element so there will be 4 pass which are shown below :

1st Pass:

"Same is the working for other pass"

2nd Pass:

3rd Pass:

4th Pass: 

And this is why the Selection Sort algorithm got its name. We select the minimum element at each pass and give it its final position.