# Python Program to Implement Selection Sort

What is 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.

Problem Description

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

Selection Sort Algorithm
```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.

Selection Sort Example

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”.
Selection Sort Algorithm Implementation

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)```
Program Explanation

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:

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
• Best Case: O(n2)
• Worst Case: O(n2)
• Average Case: O(n2)

The time complexity of the Selection Sort algorithm is O(n2) 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.

Runtime Test Cases

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”.