Monday, 26 June 2017

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]

0 comments:

Post a Comment