Python program for Selection Sort

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

Description:

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.

Algorithm for Selection Sort:

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

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 code for 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 program for Selection Sort

All Answers

Python code for Selection Sort

Python: Data Structures – Programs, Exercises, Practice, Solution

This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now