Selection sort is a sorting algorithm in which the list is considered into two parts, sorted part at left and unsorted part at right. It selects the smallest element from the unsorted list, in each iteration, and places that element at the beginning of unsorted list. Initially, the sorted part in empty, that is, the whole list is unsorted. With each iteration, the smallest element is swapped with the leftmost element of the unsorted part of the list. After required iterations, we obtain a sorted list of elements.

Illustration:

for all elements in list,step=from step=0 to step=length(list)-1
    min_idx=step
    for i from step+1 to length(list)-1 
        if value at index i < value at index min_idx
            min_idx = i
    swap as (list[step],list[min_idx])=(list[min_idx],list[step])

Time Complexity:

• Worst Case: O(n2)
• Average Case: O(n2)
• Best Case: O(n2) Space Complexity: O(1)

Program for Selection Sort:

def selectionSort(data):

    for step in range(len(data)):
        min_idx = step 

        for i in range(step + 1, len(data)):

            if data[i] < data[min_idx]: #Reversing the comparison operator will result in descending order sort 
                min_idx = i

        (data[step], data[min_idx]) = (data[min_idx], data[step])
        print("Step",step+1,"--",data)

inp=input("Enter the data: ").split()
data=[]
for i in inp:
    data.append(int(i))
selectionSort(data)
print('Sorted list in Ascending Order:')
print(data)

Output: