2 min read
Selection Sort Using Python
Last Update: 21 September, 2022Selection sort, works by repedeatly finding the lowest (minimum) in an array and putting it in the beginning. We keep track of the minimum and in each iteration and switch it with the element that the current iteration starts with.
§An Example to Help Us Understand
So let's go step by step explaining what we need to do.
Our iteration will execute for each item in our list. In the first iteration we will take the first value in the array as our default minimum value.
In our nested, second iteration we will continue iterating until we find a value smaller than our min. When we find it the new value becomes the new min and we continue like that. When the second iteration is over we end up with the lowest value as the min. Now we swap the min and the first value we selected as min in our first iteration.
In the continuing steps we keep finding the lowest value in the list and swap it with the value that the iteration is started with.
I believe an example will help us understand how it all works much better.
def selectionSort(arr, size):
for i in range(size):
min = i
for j in range(i+1, size):
if arr[j] < arr[min]:
min = j
arr[i], arr[min] = arr[min], arr[i]
data = [-2, 45, 0, 11, -9]
size = len(data)
selectionSort(data, size)
print('Sorted Array in Ascending Order:')
print(data)
Here we go! So what's happening here? In the first iteration our i value starts from 0 and goes until the length of the array minus 1. So we are iterating through the array, nothing fancy.
In the second array we start from the i+1. This means the value right next to the one we chose for the minimum. In this second array we look for a smaller value (than the arr[min]). When we find it, this new value becomes the new min. So at the end of our first loop of the second iteration our array is this:
[-9, 45, 0, 11, -2]
As you can see -9 and -2 got swapped. We keep repeating these steps until our array is sorted.
At the end of second loop:
[-9, -2, 0, 11, 45]
At the end of third loop:
[-9, -2, 0, 11, 45]
At the end of forth loop:
[-9, -2, 0, 11, 45]
At the end of fifth loop:
[-9, -2, 0, 11, 45]
Our random numbers turned out to be very easy to sort and after the second step we didn't really need to do much. However, I assume you got how selection sort works at this point. Make sure to write it on your own at least once to make sure understand instead of just memorizing it.
§Complexity of Selection Sort
As there are two loops we can simply say that the time complexity is O(N²). One loop for iterating through the array and another for comparisons.
Selection sort is memory efficient with the only used memory cost of keeping the min value. So the worst case memory used is O(1) for keeping the min and O(N) for the swaps. So if you have the time but not the space, go with selection sort.
Keep on learning!
Ilker AkbiyikTable of Contents
Related Posts
