# The array will conceptually consist of two parts, a subarray
# at the beginning representing a sorted list, and the remainder
# which is unsorted. Initially, the entire array is considered
# unsorted (this is in contrast to insertion sort). Then, in each
# pass, the minimum element is chosen and swapped to the index i
# where i = 0..len(arr)-2.
def selectionSort(arr):
    for i in range(len(arr) - 1):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
    
        if min_idx > i:
            arr[min_idx], arr[i] = arr[i], arr[min_idx]
    
    return arr