Selection sort

See Wikipedia’s article on Selection sort for explanation. Following is my implementation in Python.


def selection_sort(A):
    n = len(A)

    for i in range(0, n):
        # index of the smallest element in "input" list
        min_index = i
        for j in range(i + 1, n):
            if A[j] < A[min_index]:
                min_index = j

        if min_index != i:
            A[i], A[min_index] = A[min_index], A[i]

    return A
Complexity analysis Link to heading
  • Time: $ O(n^2) $ in the worst case scenario.


Share on:
LinkedIn