Selection Sort

The selection sort algorithm is probably one of the most intuitive sorting algorithms and the one I actually use when sorting a deck of cards. The algorithm works by iterating through the list, finding the smallest element, and moving it to the front of the array. Then, the algorithm repeats this process for the rest of the array, moving the next smallest element to the second position, and so on until the array is sorted.

The algorithm is called a selection sort because it works by repeatedly selecting the smallest remaining element.

def selection_sort(arr):
    for i in range(len(arr)):
        min_index = i
        # Find the index of the smallest element in the unsorted portion of the array.
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]

Just like the bubble sort, the selection sort is an in-place sorting algorithm and has a time complexity of $O(n^2)$ and a space complexity of $O(1)$.