# Selection Sort using Recursion¶

## Iterative implementation¶

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

In [1]:

Copied!

```
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]:

Copied!

```
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]:

Copied!

```
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]:

Copied!

```
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]