PUBLISHED ON: AUGUST 16, 2021
Python Program for Selection Sort
Selection sort is a sorting algorithm that picks the smallest element from an unsorted list and sets it at the top of the unsorted list in each iteration. In this tutorial, we will perform a selection sort algorithm to sort an array.
Selection Sort - Basic Introduction
The concept behind the selection sort algorithm is to identify the smallest element in an array and sort it accordingly. The selection sort algorithm is an in-place comparison-based method that divides the input array into two sections: a sorted array on the left and an unsorted array on the right. Let us have a rough sketch of selection sorting:
- Assign the minimum value to array index 0
- Search Smallest element input in an array
- Swap with value at the location of minimum value
- Increment minimum value to point next element
- Repeat until the array is sorted
Now for a better understanding look at the diagram below:
Algorithm
As of now, we have a rough understanding of the selection sort. Let us now have a look at the algorithm followed by the code for a better understanding:
- Create a function Selection_Sort that takes an array as an argument
- Create a loop with a loop variable i that counts from 0 to the length of the array – 1
- Declare smallest with the initial value i
- Create an inner loop with a loop variable j that counts from i + 1 up to the length of the array – 1.
- if the elements at index j are smaller than the element at index smallest, then set smallest equal to j
- swap the elements at indexes i and smallest
- Print the sorted list
Python Program
As discussed above in the algorithm, let us now dive into the programming part of the Selection Sort operation influenced by the algorithm. In this program user can input the list by giving whitespace in the console part:
def Selection_Sort(array):
for i in range(0, len(array) - 1):
smallest = i
for j in range(i + 1, len(array)):
if array[j] < array[smallest]:
smallest = j
array[i], array[smallest] = array[smallest], array[i]
array = input('Enter the list of numbers: ').split()
array = [int(x) for x in array]
Selection_Sort(array)
print('List after sorting is : ', end='')
print(array)
Enter the list of numbers: 2 4 1 3 5
List after sorting is : [1, 2, 3, 4, 5]
Conclusion
In this tutorial, we have performed a Selection Sort operation in python to sort an array. The selection can be used to sort the small list. The time complexity of the selection sort is O(n2) and the space complexity is O(1).