Home » Python » Python programs

# Python program for Selection Sort

**Selection Sort in Python**: Here, we are going to learn to implement Selection sort in an array or list in Python.

Submitted by Soumya Sinha, on December 27, 2020

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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions