Nishant Kumar
Cosmic Techie

Cosmic Techie

Selection Sort

Nishant Kumar's photo
Nishant Kumar
·Jan 24, 2022·

1 min read

Selection Sort

Subscribe to my newsletter and never miss my upcoming articles

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:

SelectionSort.gif

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:

selectionsort.png

 
Share this