Selection Sort

#algorithm #computer-science

There are many different ways to sort an array. Here’s a simple one, called selection sort:

1. Find the smallest element. Swap it with the first element.
2. Find the second-smallest element. Swap it with the second element.
3. Find the third-smallest element. Swap it with the third element.
4. Repeat finding the next-smallest element, and swapping it into the correct position until the array is sorted. This algorithm is called selection sort because it repeatedly selects the next-smallest element and swaps it into place. When the first element is found and relocated, the remaining elements are called a subarray. Below is the Python implementation of the selection sort algorithm.

def findMinIndex(arr, start):
    min_idx = start
    for i in range(start + 1, len(arr)):
        if arr[i] < arr[min_idx]:
            min_idx = i
    return min_idx

def Swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = findMinIndex(arr, i)
        Swap(arr, i, min_idx)

Sources:

1. Khan Academy