Python - Selection Sort Algorithm Implementation

Selection sort algorithm - In this article, we will learn about another sorting algorithm - Selection sort. Just like Bubble sort, time complexity of this algorithm is O(n^2) and space complexity being O(1).

Selection Sort Algorithm

i = 0

while i < length(array)
begin
    search for minimum element in the list array[i:]
    exchange the minimum element with array[i]
    increment i by 1
end

Example

Consider the following list-

Iteration 1:

Iteration 2:

Iteration 3:

Iteration 4:

Iteration 5:

Iteration 6:

Iteration 7:

Iteration 8:

Python Implementation:

def selection_sort(array):
    n = len(array)
    
    for i in range(n):
        
        # Index of smallest element
        min_index = i
        
        for j in range(i+1, n):
            if array[j] < array[min_index]:
                min_index = j
                
        array[min_index], array[i] = array[i], array[min_index]
        
my_array = [5, 3, 7, 1, 4, 8, 2, 6]
selection_sort(my_array)
print my_array

Output:

[1, 2, 3, 4, 5, 6, 7, 8]