Selection sort

Selection sort is an in-place sorting algorithm.

Time complexity :

Average case : O(n2)

Best case : O(n2)

Worst case : O(n2)

Worst case space complexity : O(n)

How the algorithm works:

  • The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right in the list.

  • Initially, the sorted sublist (starting at the left side) is empty and the unsorted sublist is the entire input list.

  • On every iteration, the algorithm finds the smallest element in the unsorted sublist and swaps it with the leftmost unsorted element (putting it in sorted order), and increments the sorted sublist boundary one element to the right.

Implementation in Python :

def selectionsort(list):
    for jx in range(0,len(list)-1):
        min = jx
        for ix in range(jx+1,len(list)):
            if list[ix] < list[min]:
                min = ix
        if min != jx:
            temp = list[jx]
            list[jx] = list[min]
            list[min] = temp
    
    return list
if __name__ == "__main__":
    print(selectionsort([2,1,3,0,-1,-3,-2,5,6,4]))

Output :

[-3, -2, -1, 0, 1, 2, 3, 4, 5, 6]

Links: