Python Program to Implement Selection Sort

Selection Sort in Python is a sorting algorithm that iterates through a list, finds the minimum element, and swaps it with the current position. This process is repeated until the list is sorted.

Write a program that sorts a list by implementing selection sort.

def selection_sort(arr):
    n = len(arr)
    for i in range(n-1):
        min_index = i
        for j in range(i+1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]

In this code, arr represents the input list to be sorted. The algorithm iterates through the list and finds the minimum element in each iteration, swapping it with the current position. This process continues until the list is sorted in ascending order.

Here’s a step-by-step explanation of how the Selection Sort algorithm sorts the list “3 1 4 5 2 6” in ascending order:

• Start with the given list: “3 1 4 5 2 6”.
• Find the minimum element in the list, which is 1.
• Swap the minimum element (1) with the first element (3), resulting in “1 3 4 5 2 6”.
• Move to the next position and find the minimum element, which is 2.
• Swap the minimum element (2) with the second element (3), resulting in “1 2 4 5 3 6”.
• Repeat this process until the list is sorted completely.
• After applying the Selection Sort algorithm, the sorted list will be “1 2 3 4 5 6”.

Here is the source code of a Python program to implement selection sort. The program output is shown below.

def selection_sort(alist):
    for i in range(0, len(alist) - 1):
        smallest = i
        for j in range(i + 1, len(alist)):
            if alist[j] < alist[smallest]:
                smallest = j
        alist[i], alist[smallest] = alist[smallest], alist[i]
 
 
alist = input('Enter the list of numbers: ').split()
alist = [int(x) for x in alist]
selection_sort(alist)
print('Sorted list: ', end='')
print(alist)

1. Create a function selection_sort that takes a list as argument.
2. Inside the function create a loop with a loop variable i that counts from 0 to the length of the list – 1.
3. Create a variable smallest with initial value i.
4. Create an inner loop with a loop variable j that counts from i + 1 up to the length of the list – 1.
5. Inside the inner loop, if the elements at index j is smaller than the element at index smallest, then set smallest equal to j.
6. After the inner loop finishes, swap the elements at indexes i and smallest.
7. The sorted list is displayed.

Time Complexity of Selection Sort Algorithm:

• Best Case: O(n²)
• Worst Case: O(n²)
• Average Case: O(n²)

The time complexity of the Selection Sort algorithm is O(n²) in all cases, where “n” is the number of elements in the list. This is because it involves nested loops where each element is compared with all the remaining elements.

Space Complexity: O(1)
The space complexity is O(1) as the algorithm operates on the input list in-place without requiring any additional space that grows with the input size.

Testcase 1: Here, the elements are entered in random order.

Enter the list of numbers: 3 1 4 5 2 6
Sorted list: [1, 2, 3, 4, 5, 6]

Testcase 2: In this case, the user enters the list of numbers as “2 10 5 38 1 7”, and the program will output:

Enter the list of numbers: 2 10 5 38 1 7
Sorted list: [1, 2, 5, 7, 10, 38]

Testcase 3: In this scenario, the elements are entered in reverse sorted order.

Enter the list of numbers: 5 3 2 1 0
Sorted list: [0, 1, 2, 3, 5]

To practice programs on every topic in Python, please visit “Programming Examples in Python”.