Write a Program to Perform Selection Sort in Python

Introduction

Selection sort is one of the sort techniques for sorting array based data. The name selection because it selects the smallest element in each iteration and places it in the right position as per the sorting manner(ascending or descending) that the users want to perform. In this tutorial, you'll learn how to perform selection sort in python.

How Selection Sort Works

Step 1

Step 2

Step 3

Step 4

Algorithm for Selection Sort

length = Length of the Array
for i in (0 to length-1)
    min_index = i
    for j in (i+1 to length)
    # For desecding order: change '<' to '>'
        check if array[j] < array[min_index]
            if yes, set min_index = j
    swap between array[i] and array[min_index]

Code

'''Write a python program for selection sort'''
def SelectionSort(array):
    for i in range(len(array)):
        min = i
        for j in range(i+1, len(array)):
            # Put '>' to perform this sort 
            # in the descending order
            if array[j] < array[min]:
                min = j
        # Swap the min value with the higher value
        array[i], array[min] = array[min], array[i]
# The main function
if __name__ == "__main__":
    arr = [13, 9, 11, 8, 4, 6]
    SelectionSort(arr)
    print("----The Sorted data----")
    print(arr)

Output

----The Sorted data----
[4, 6, 8, 9, 11, 13]

Selection Sort with user input

Code

'''program for 
selection sort in python with user input'''
def SelectionSort(array):
    for i in range(len(array)):
        min = i
        for j in range(i+1, len(array)):
            # Put '>' to perform this sort 
            # in the descending order
            if array[j] < array[min]:
                min = j
        # Swap the min value with the higher value
        array[i], array[min] = array[min], array[i]
# The main function
if __name__ == "__main__":
    arr = input("Enter the array data, separated by comma: ").split(',')
    arr = [int(i) for i in arr]
    SelectionSort(arr)
    print("----The Sorted data----")
    print(arr)

Output

Enter the array data, separated by comma: 13,9,11,8,4,6
----The Sorted data----
[4, 6, 8, 9, 11, 13]

Complexity analysis

There are three conditions the array may have: In ascending order, descending order, or random order. One of the interesting things about the selection sort is, for worst, average, or best case, the time and space complexity is the same.

Time Complexity

Worst Case: O(n^2)

Average Case: O(n^2)

Best Case: O(n^2)

Space Complexity

For all conditions: O(1)