Selection Sort

About

The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order)

from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array:

1) The subarray which is already sorted.

2) Remaining subarray which is unsorted.

In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.

Complexity

Time Complexity:O(n2) as there are two nested loops.

Auxiliary Space:O(1)
The good thing about selection sort is it never makes more than O(n) swaps and can be useful when memory write is a costly operation.

Code

Ascending order

#Declare the array
A = [64, 25, 12, 22,11]

#For the length of A
for i in range(len(A)):
    min_index = i #Get initial minimal value (initially in index 0)

    for j in range(i+1, len(A)):#For one position after the index i
        if A[min_index] > A[j]: #If the value of the position J is less than the current
            min_index = j #Save the new index

    A[i], A[min_index] = A[min_index], A[i] #And swipe the values

print A

#Output:
# [11, 12, 22, 25, 64]

Descending order

#Same as above, but

A = [64, 25, 12, 22,11]

for i in range(len(A)):
    min_index = i

    for j in range(i+1, len(A)):
        if A[min_index] < A[j]:  #Now the order will me decreasing 
            min_index = j

    A[i], A[min_index] = A[min_index], A[i]

print A

#Output:
# [64, 25, 22, 12, 11]