Signup/Sign In

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:

Selection Sort

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