Write a Python program to sort a list of elements using the selection sort algorithm

Selection Sort algorithm is an in-place comparison-based algorithm. The algorithm divides the array into two segments:

• The sorted part at the left end.
• The remaining unsorted part at the right end.

The algorithm involves finding the minimum or maximum element in the unsorted portion of the array and then placing it in the correct position of the array.

Python Data Structures and Algorithms: Selection sort

Last update on January 04 2021 14:03:04 (UTC/GMT +8 hours)

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:

1. Assign the minimum value to array index 0
2. Search Smallest element input in an array
3. Swap with value at the location of minimum value
4. Increment minimum value to point next element
5. 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:

1. Create a function Selection_Sort that takes an array as an argument
2. Create a loop with a loop variable i that counts from 0 to the length of the array – 1
3. Declare smallest with the initial value i
4. Create an inner loop with a loop variable j that counts from i + 1 up to the length of the array – 1.
5. if the elements at index j are smaller than the element at index smallest, then set smallest equal to j
6. swap the elements at indexes i and smallest
7. 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).

What is Selection Sort?

SELECTION SORT is a comparison sorting algorithm that is used to sort a random list of items in ascending order. The comparison does not require a lot of extra space. It only requires one extra memory space for the temporal variable.

This is known as in-place sorting. The selection sort has a time complexity of O(n2) where n is the total number of items in the list. The time complexity measures the number of iterations required to sort the list. The list is divided into two partitions: The first list contains sorted items, while the second list contains unsorted items.