Home » Python » Python Programs

Python Program for Selection Sort

Selection Sort in Python: In this tutorial, we will learn about the selection sort, its implementation, how to implement selection sort in an array or list in Python. By Soumya Sinha Last updated : April 21, 2023

What is Selection Sort?

The selection sorting algorithm repeatedly searches for the smallest element (considering we want to sort the list in non-decreasing order) in the unsorted list (i.e. remaining elements) and move that particular element to its final correct position.

This algorithm is an in-place comparison sorting algorithm, thus the number of swaps in this algorithm will not be more than the number of elements in the list. In this article, we will consider that we need to sort the given list in non-decreasing order.

Here in this algorithm, the input list is divided into two parts:

• A sorted sublist(built from left to right ) of elements starts at the left end of the list.
• An unsorted sublist of elements occupies the rest of the list.

Note: Initially, the sorted sublist is empty and the unsorted sublist is the whole input list.

In every iteration, the algorithm finds the smallest element in the unsorted list and swaps it with the leftmost unsorted element. And after every swap length of the sorted sublist will increase by one and that of the unsorted sublist will decrease by one.

Pseudocode for Selection Sort

The procedure of selection sort is as follow,

Selection_Sort (arr):
   n =len(arr)
   For i=0 to n:
       min_index = i
       For j=i+1 to n:
           If arr[min_index] > arr[j]:
                min_index = j
       Swap(arr[i],arr[min_index])

Selection Sort Example

Consider an array < 12, 4, 6, 1, 5>.

Initially min_index = 0. Now we will compare arr[min_index] with all the other elements in the unsorted sublist and store the value of the index of the smallest element in the unsorted sublist in the min_index variable. Here 1 is the smallest element so we will swap 12 and 1.

<1, 4, 6, 12, 5>

Now min_index = 1. We will again repeat the same process but this time we won't swap as the smallest element 4 is already in its correct position.

<1, 4, 6, 12, 5>

Now min_index = 2. We will again repeat the same process and this time the minimum element is 5 and we need to place it in its correct position that is at index 2, so we will swap 6 and 5.

<1, 4, 5, 12, 6>

Repeat the same process and swap 12 and 6 to obtain the sorted list.

<1, 4, 5, 6, 12>

Time Complexity: O(n^2)

Python program to implement selection sort

import sys

def selection_sort(arr):
    # This function will sort the array in non-decreasing order. 
    n = len(arr)
    #The outer loop will run for n times.
    for i in range(n):
        min_index = i
        # The inner loop will run for n-i-1 times as the
        # first i elements are already in sorted.
        for j in range(i+1, n):
        # Compare if the present element is smaller than the
        #  element present at min_index in the array. If yes
        # store the index of the present element in min-index.
            if arr[min_index] > arr[j]:
                min_index = j
        # Swap the ith element with the smallest element in the
        # unsorted list i.e. arr[min_index}].
        if i != min_index:
            temp = arr[i]
            arr[i] = arr[min_index]
            arr[min_index] = temp 
    return arr
    
# main code
if __name__=='__main__':

    arr = [21, 15, 96, 37, 72, 54, 68, 41, 85, 30]
    print("Sorted array: ")
    print(selection_sort(arr))

Output

Sorted array: 
[15, 21, 30, 37, 41, 54, 68, 72, 85, 96]

Python Data Structure Programs »