Search⌘ K
Home
Courses
Recursion for Coding Interviews in Python

Solution Review: Sort an Array

Explore the recursive approach to sorting arrays using the bubble sort algorithm. Learn how recursion reduces the array size, establishes base cases, and places elements in order. This lesson helps you understand the flow of recursive calls and prepares you for applying recursion to array problems.

We'll cover the following...

Solution: Using Recursion

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

Python 3.5
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 ...