Solution Review: Sort an Array

This review provides a detailed analysis of the solution to sort an array.

We'll cover the following

Solution: Using Recursion

The following solution sorts the array recursively. It is commonly known as Bubble sort algorithm

Press + to interact
def sort(testVariable, length):
	# Base case
	if length <= 1 :
		return
	
	# Recursive case
	# Sort first n-1 elements
	sort(testVariable, length - 1)
	# Insert last element at its correct position in sorted array
	lastElement = testVariable[length - 1] # fetch the last element
	temp = length - 2 # start finding its correct location from one element before it
	
	# Move elements of testVariable[0..i-1], that are greater than key, to one position ahead of their current position 
	while (temp >= 0 and testVariable[temp] > lastElement):
		testVariable[temp + 1] = testVariable[temp]
		temp = temp - 1
	testVariable[temp + 1] = lastElement # place the element in its correct position
# Driver Code
testVariable = [5, 4, 2, 3, 1]
print("Original Array ---> " + str(testVariable))
sort(testVariable, len(testVariable))
print("Modified Array ---> " + str(testVariable))

Explanation

In the code snippet above, we reduce the length of the input array testVariable in each recursive call. When the length reaches 11, we return because array of size 11 is always sorted. This is also our base case. Now when the child recursive call returns, we fit the last element reached in its correct position.

Note, that we are traversing the array from the right side to left side. This means that the last element in our case is actually the first element

Traversing array
Traversing array

After the child recursive function returns we insert the last element at its correct position in the sorted array.

Let’s have a look at the sequence of function calls:

In the next lesson, we have a small quiz for you to test your understanding of recursion with arrays.