Python Selection Sort Algorithm: Explained with Examples, Code and Video
The next sorting algorithm explained is the selection sort algorithm.
Selection Sort Algorithm in Python
The selection sort algorithm is a simple sorting algorithm that works by repeatedly swapping the lowest remaining number in the list into the lowest available place.
Starting from the list beginning at index 0, it finds the lowest number and swaps this number with the current element. It then moves to position1 and swaps this element with the next lowest number.
The technique is likened to how a person might order a hand of playing cards.
for i in range(len(nums)):
min_index = i
for j in range(i+1, len(nums)):
if nums[min_index] > nums[j]:
min_index = j
nums[i],nums[min_index] = nums[min_index],nums[i]Phone users can swipe the screen to move sideways to view the code
Selection Sort Algorithm Example
We show a simple example of the selection sort algorithm in python with the unordered list of six numbers.
The first stage finds the lowest number and swaps it into the first position which is the element with the index 0.
In this example the lowest number is one, therefore 1 is swapped with the number in the first place in the list, which is the number 7.
Next, the next lowest number is swapped into the next position, at index 1. The number 2 is swapped with the the number 7.
The next pass finds the lowest remaining number of 3 and puts it in the lowest remaining list position, resulting in the ordered elements of 1,2 and 3.
The number 4 is in the correct place in the list, therefore the only remaining change sees the final two numbers swapped so that the number 7 is correctly before the final and highest number 8.
Video Tutorial
Selection Sort in Python Explained
The selection sort locates the lowest number and swaps this to the lowest place in the list that has not already been ordered. Thus we have the ‘ordered’ and unordered’ parts of the list.
#swap numbers
nums[i],nums[min_index] = nums[min_index],nums[i]The python code that swaps elements in the selection sort, swaps the lowest number, at index min_index, and the element at the lowest unordered position at i.
The variable min_index starts at the beginning of the unordered elements and is used to compare the following elements to find the lowest reamining number.
min_index = i
for j in range(i+1, len(nums)):
#find lowest
if nums[min_index] > nums[j]:
min_index = jThe for loop starts at the place after i and checks the remaining numbers to see if any of them are lower than the current lowest number.
The default lowest number will be the number at nums[i], the lowest unordered position, and if there are no other lower numbers then the loop will move to the next iteration.
nums = [7,1,8,4,3,2]
for i in range(len(nums)):
#look in unordered – find lowest number
print(nums)
min_index = i
for j in range(i+1, len(nums)):
#find lowest
if nums[min_index] > nums[j]:
min_index = j
#swap with nums[i]
nums[i],nums[min_index] = nums[min_index],nums[i]output
[7, 1, 8, 4, 3, 2]
[1, 7, 8, 4, 3, 2]
[1, 2, 8, 4, 3, 7]
[1, 2, 3, 4, 8, 7]
[1, 2, 3, 4, 8, 7]
[1, 2, 3, 4, 7, 8]
The code can be downloaded and copied from this text file – selection_sort.txt
Is the Selection Sort Algorithm Efficient?
Although we still iterate through two loops, and have a worst case complexity of O(n 2), the selection sort is more efficient than the bubble sort
We will compare the first three sorting algorithms in python to see how efficient they are in terms of time to run. The results will be published in this article below.
