Hello everyone, welcome back to Programming In Python! In continuation of the algorithm series here is one of the sorting algorithms. Here in this post, I will discuss on Selection Sort algorithm and how to implement Selection Sort in Python.
In Selection Sort algorithm, the smallest element is searched and placed at the starting of the list by swapping the smallest element found with the first element of the list. So here, the list has 2 parts, one is sorted and the other is unsorted. Initially, the whole list is unsorted, but when each swapping occurs the leftmost part of the list becomes sorted and continues until the whole list is sorted.
You can also watch the video on YouTube here.
Time Complexity Of Selection Sort
| Best Case | O(n2) |
| Average Case | O(n2) |
| Worst Case | O(n2) |
Algorithm
Given a list L of n elements with values or records L0, L1, …, Ln-1, bubble sort is applied to sort the list L.
- Find the smallest element in the array
- Swap the position(index) of the first element with the smallest element
- Repeat step 1 from the 2nd element in the array and continue until all elements are sorted
- Return the final sorted list.
Ad:
Learn Python Programming Masterclass – Enroll Now.
Udemy
Selection Sort Algorithm – Code Visualization
Program
__author__ = 'Avinash'
def selection_sort(sort_list):
for i in range(len(sort_list)):
smallest_element = min(sort_list[i:])
index_of_smallest = sort_list.index(smallest_element)
sort_list[i], sort_list[index_of_smallest] = sort_list[index_of_smallest], sort_list[i]
print('\nPASS :', i + 1, sort_list)
print ('\n\nThe sorted list: \t', sort_list)
lst = []
size = int(input("\nEnter size of the list: \t"))
for i in range(size):
elements = int(input("Enter the element: \t"))
lst.append(elements)
selection_sort(lst)
Output
Please feel free to look at other sorting algorithms here or all the algorithms here.