How to Use Selection Sort Using Python?

Sorting is one of the most important concepts in the data structure, it solves the basic yet very vital problem for computer science, the best thing about learning sorting algorithm is that it helps to build the logic step by step, each algorithm is better or worse than the other one in some sense, as of now we will concentrate our focus on selection sort algorithm.

 

Out of many sorting algorithms, selection sort seems to be very easy to understand, but how does it perform? Is selection sort better than insertion sort? What is the time complexity of the Selection sort? These questions will be answered while we will analyze this sorting algorithm in detail.

 

(Must read: Machine Learning algorithms)

 

Selection sort Algorithm

 

Selection sort is a sorting algorithm, specifically an in-place comparison sort, just like the insertion sort. If the elements to sort are low, i.e in the range of 10-20, selection sort is among the fastest sorting algorithms. 

 

This algorithm focuses on finding the minimum elements and then placing them one by one from the starting point of an array and because the minimum elements are swapped with their correct position, the selection sort algorithm is not stable.

 

The working of selection sort doesn’t require any additional space and it is also scalable

 

The algorithm works as follow:

 

1. Find the minimum value in the list.

2. Swap it with the value in the first position.

3. Repeat the steps above for the remainder of the list (starting at the second position and advancing each time).

 

(Related blog: Merge and bubble sort)

 

Selection Sort Example

 

This is one of the simplest and the most intuitive sorting algorithms, let us take an example to understand the working of selection sort-:

---

---

Let us say the above array is named as ‘A’, all we need to find is the minimum element one by one, for example, the minimum element in the array ‘A’ as of now is ‘1’, therefore swap the first minimum element in an array with the ‘0th’ index, or the first index, see the below image for better understandability.

---

---

Now, we will find the next minimum element in array A and swap it with the second element in the array.

---

---

The next minimum element in array A is 3, therefore this element will be placed at the third index. 

---

---

Similarly, the other three steps will find the other minimum values from the array ‘A’ and will swap them with their respective index, in this way, in each iteration we are sorting one more element, and eventually, the whole list is sorted. 

 

Selection Sort Analysis

 

Selection sort is not difficult to analyze compared to other sorting algorithms, since none of the loops depend on the data in the array; selecting the lowest element requires scanning all n elements ( this takes n-1 comparisons) and then swapping it into the first position. 

 

Finding the next lowest element requires scanning the remaining n-1 elements and so on, for (n-1) + (n-2)+ …… +2 + 1 = n(n-1)/2, which is Ө(n2) comparisons.

 

Each of these scans requires one swap for n-1 elements because the final element is already in place.

 

(Also read: Types of Binary Trees)

 

 

Selection Sort Python Implementation

 

A = [4,2,3,1,5,8,6]

def Selecsort(A):

    for i in range(0,len(A)-1):

        minimum = i

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

            if A[j]<A[minimum]:

                minimum = j

                

        A[i],A[minimum]= A[minimum],A[i]

 

The above code is very simple, we have taken an array that we need to sort, this array contains 7 elements inside it. A function is defined that takes an array ‘A’ as a parameter. 

 

Inside the function, an outer for loop is taken which will make sure that each and every element is sorted inside the array, this loop is starting from the first element, i.e the 0th index and ends at the 6th index (total length - 1, because index in python starts from 0). 

 

(Recommended: Linear Search And Binary Search Using Python)

 

Inside the first loop, we have taken a variable name minimum to store the minimum value in an array, initially ‘i’ is assumed to be the minimum value in an array. This variable is used to select the minimum value in every iteration or after each pass. 

 

The next loop(jth loop) is used in order to implement swapping of the minimum element to its respective index and it starts from i+1 to the total length of the array. Inside the jth loop, we will check for the minimum value, and if we find one, we will swap that element to the first index initially. 

 

Time Complexity of Selection Sort

 

The time complexity of the selection sort can be determined by how many operations are being performed inside the function, the best case complexity for the selection sort is when the array is already sorted because only comparisons happen in this case but no swaps. 

 

The total number of comparisons in the best case of selection sort is ‘n-1’  in the first pass because the first element is compared with the remaining elements. 

 

In the next pass, we will compare ‘n-2’ elements, therefore the comparisons go like, n-1,n-2,n-3,.....0 or the other way around is, 0 + 1 + 2 + …… n-1, which is nothing but n(n-1)/2, if we remove constants and drop lower-order constants, the complexity of the selection sort in the best case becomes o(n2).

 

(Recommended: Partition Algorithm and QuickSort Algorithm)

 

The worst-case time complexity of selection sort will happen when we need to sort the list in ascending order, but we get the list in descending order. The number of comparisons in the worst-case for selection sort is o(n2), but here we also need to count the number of swaps. 

 

The total number of swaps will be equal to the number of elements in an array, therefore we will get the complexity of o(n) for the total number of swaps in the worst-case selection sort. 

 

As we can see, o(n2) is the highest order among comparison complexity and swap complexity, therefore we will neglect o(n) and the complexity of selection sort in the worst-case is o(n2). 

 

The average case of selection sort is also o(n2) as the number of comparisons remains the same, and obviously in any case the swap complexity cannot be more than the worst-case.

 

(Recommended reading: How does Basic Convolution Work for Image Processing?)

 

 

Conclusion

 

In this blog, we have learned about the selection sort algorithm in-depth, each and every step needed for the working of selection sort is evaluated. With the help of illustration, it became easy to understand the implementation of selection sort, and the python code for selection sort was easily understood. 

 

In the last section of the blog, we analyzed the complexity of the selection sort algorithm in detail.