Selection sort is an in-place comparison sorting algorithm. It has an O(n²) time complexity, which makes it inefficient on large lists, and generally performs worse than the similar insertion sort. In this tutorial, I will show you how to implement selection sort using python. Also, show you the time complexity of this algorithm.
The main funda of selection sort is selecting a value that is either maximum or minimum. Then compare this value with others. If the value is in the wrong place then swap the value with others.
Well, implement the selection sort first take an array or list that stored unsorted values. Let’s see the following code. I will explain you a bit later.
Selection sort algorithm
def selection_sort(arr, mode='asc'): l = len(arr) for i in range(0, l): min_index = i for j in range(i+1, l): if mode == 'asc': if arr[min_index] > arr[j]: min_index = j elif mode == 'dsc': if arr[min_index] < arr[j]: min_index = j if i != min_index: arr[i], arr[min_index] = arr[min_index], arr[i]
Well, above you can see a function that is our selection sort function. Let’s explore this function. You can see this function takes two parameters. There is an array or list and another one is a mode. The mode parameter is totally optional. You can take this parameter or may not.
Inside this function, first I took a variable to store the length of the array or list. Then execute a loop from zero to the length of the list. Inside the loop, initially assume the first value is minimum. Then compare this value with other values. If this value isn’t the minimum then find the minimum value from the list. To do that, you have to execute another loop.
Well, then check if the first index value is not equal to the index of the minimum value, then swap two values.
The time complexity of this algorithm is O(n^2). You can see in this function, we execute two loops that are travers from zero to N.