Selection Sort using Recursion¶

Iterative implementation¶

• Just to get back the intuition of how selection sort works

In [1]:

def selection_sort(arr):

    for i in range(len(arr)):
        min_element = arr[i]
        min_idx = i
        for j in range(i + 1, len(arr)):
            if min_element > arr[j]:
                min_element = arr[j]
                min_idx = j

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

    return arr

def selection_sort(arr): for i in range(len(arr)): min_element = arr[i] min_idx = i for j in range(i + 1, len(arr)): if min_element > arr[j]: min_element = arr[j] min_idx = j arr[min_idx], arr[i] = arr[i], arr[min_idx] return arr

In [2]:

arr = [10, 1, 29, 8, 4, 57, 6]
selection_sort(arr)

arr = [10, 1, 29, 8, 4, 57, 6] selection_sort(arr)

Out[2]:

[1, 4, 6, 8, 10, 29, 57]

In [6]:

def selection_sort_recursive(arr):

    # 1. Base case
    # if length of array is less than 1
    # no need to sort, just return the array
    if len(arr) < 1:
        return arr

    # 2. Processing
    # assume 1st element is minimum
    min_element = arr[0]
    min_idx = 0

    # Remember from the iterative version
    # that the first for loop is for the
    # number of rounds it takes to sort the
    # array which is (n-1) as the first element
    # gets sorted in the 0th round. This is now
    # being taken care by recursion.
    # The second for loop is used to find out the minimum
    # element from the remaining array (arr[1:]) as
    # the first element is assumed to be minimum.
    for i in range(len(arr[1:]) + 1):
        if min_element > arr[i]:
            min_element = arr[i]
            min_idx = i

    # swap the element found at the min index
    # with 0th element
    arr[0], arr[min_idx] = arr[min_idx], arr[0]

    # 3. Recursive relation
    # what's happening here?
    # since the first element is sorted in the sub-array
    # so we build the remaining array by adding the sub array
    # each time. Send the remaining array to solve with
    # recursion.
    # Each time we just compare 2 elements of the sub-array
    # 0th element and the 1st of the remaining array

    remaining = [arr[0]] + selection_sort_recursive(arr[1:])

    return remaining

def selection_sort_recursive(arr): # 1. Base case # if length of array is less than 1 # no need to sort, just return the array if len(arr) < 1: return arr # 2. Processing # assume 1st element is minimum min_element = arr[0] min_idx = 0 # Remember from the iterative version # that the first for loop is for the # number of rounds it takes to sort the # array which is (n-1) as the first element # gets sorted in the 0th round. This is now # being taken care by recursion. # The second for loop is used to find out the minimum # element from the remaining array (arr[1:]) as # the first element is assumed to be minimum. for i in range(len(arr[1:]) + 1): if min_element > arr[i]: min_element = arr[i] min_idx = i # swap the element found at the min index # with 0th element arr[0], arr[min_idx] = arr[min_idx], arr[0] # 3. Recursive relation # what's happening here? # since the first element is sorted in the sub-array # so we build the remaining array by adding the sub array # each time. Send the remaining array to solve with # recursion. # Each time we just compare 2 elements of the sub-array # 0th element and the 1st of the remaining array remaining = [arr[0]] + selection_sort_recursive(arr[1:]) return remaining

In [4]:

arr = [10, 1, 29, 8, 4, 57, 6]
selection_sort_recursive(arr)

arr = [10, 1, 29, 8, 4, 57, 6] selection_sort_recursive(arr)

Out[4]:

[1, 4, 6, 8, 10, 29, 57]