from typing import List


def selection_sort(arr: List[int]) -> List[int]:
    """
    Selection Sort Algorithm

    T(N):
            Best Case:  Ω(n^2)

            Avg. Case:  Θ(n^2)

            Worst Case: O(n^2)

    S(N):   O(1)    Best for cases when we are short on memory space.

    :param arr: An unsorted array of n elements
    :return:    sorted Array
    """
    n = len(arr)

    for i in range(n):
        min_idx = i

        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j

        arr[i], arr[min_idx] = arr[min_idx], arr[i]

    return arr