I have to sort an array using insertion sort and using recursion without using loops. I have tried but it is not sorting anything. Here is my code:
def recursiveInsertionSort(array, i, j):
n = len(array)
if i < n:
temp = array[i]
j = i - 1
if j >= 0 and array[j] > temp:
array[j 1] = array[j]
recursiveInsertionSort(array, i, j - 1)
array[j 1] = temp
recursiveInsertionSort(array, i 1, j)
return array
arr = [10, 8, 7, 50, 60, 3, 9, -1]
print(recursiveInsertionSort(arr, 1, 0))
Output is [10, 8, 7, 50, 60, 3, 9, -1] same as the given array. Expected output is [-1, 3, 7, 8, 9, 10, 50, 60] Can anyone help me to find where the problem is?
CodePudding user response:
Honestly there are too many mistakes in your code for me to list off, but this works:
def recursiveInsertionSort(array, i, j):
n = len(array)
if i < n and j >= 0:
if array[j] > array[j 1]:
temp = array[j 1]
array[j 1] = array[j]
array[j] = temp
recursiveInsertionSort(array, i, j - 1)
if j == 0:
recursiveInsertionSort(array, i 1, i)
return array
arr = [10, 8, 7, 50, 60, 3, 9, -1]
print(recursiveInsertionSort(arr, 1, 0))
Output:
[-1, 3, 7, 8, 9, 10, 50, 60]
CodePudding user response:
Recursion is a functional heritage and so using it with functional style yields the best results. This means avoiding things like mutation, variable reassignments, and other side effects.
We can write insertion_sort(t)
using inductive reasoning. Starting with the input source src = t
and an empty destination array dst = []
-
- If
src
is empty, there is nothing left to sort. Return thedst
array - (inductive)
src
has at least one element.insert
the first elementsrc[0]
intodst
and recur on the sub-problemsrc[1:]
def insertion_sort(t):
def run(src, dst):
if not src:
return dst # 1
else:
return run(src[1:], insert(dst, src[0])) # 2
return run(t, [])
insert(t, x)
can be written using the same technique -
- If the input
t
is empty, the only possible output is[x]
- (inductive)
t
has at least one element. If the first elementt[0]
is less than the element to insertx
, then prependt[0]
to the result of the recursive sub-probleminsert(t[1:], x)
- (inductive)
t
the first element is greater than or equal tox
. Prependx
tot
def insert(t, x):
if not t:
return [x] # 1
elif t[0] < x:
return [t[0]] insert(t[1:], x) # 2
else:
return [x] t # 3
Finally print the result
arr = [10, 8, 7, 50, 60, 3, 9, -1]
print(insertion_sort(arr))
[-1, 3, 7, 8, 9, 10, 50, 60]
visualize
Writing out the evaluation steps can help aid our ability to visualize how recursive computations grow. First we look at the simpler of the two, insert(t,x)
insert([3, 7, 8, 10, 50, 60], 9)
== [3] insert([7, 8, 10, 50, 60], 9)
== [3] [7] insert([8, 10, 50, 60], 9)
== [3] [7] [8] insert([10, 50, 60], 9)
== [3] [7] [8] [9] [10, 50, 60]
== [3, 7] [8] [9] [10, 50, 60]
== [3, 7, 8] [9] [10, 50, 60]
== [3, 7, 8, 9] [10, 50, 60]
== [3, 7, 8, 9, 10, 50, 60]
And now let's visualize insertion_sort(t)
-
insertion_sort([10, 8, 7, 50, 60, 3, 9, -1])
== run([10, 8, 7, 50, 60, 3, 9, -1], [])
== run([8, 7, 50, 60, 3, 9, -1], [10])
== run([7, 50, 60, 3, 9, -1], [8, 10])
== run([50, 60, 3, 9, -1], [7, 8, 10])
== run([60, 3, 9, -1], [7, 8, 10, 50])
== run([3, 9, -1], [7, 8, 10, 50, 60])
== run([9, -1], [3, 7, 8, 10, 50, 60])
== run([-1], [3, 7, 8, 9, 10, 50, 60])
== run([], [-1, 3, 7, 8, 9, 10, 50, 60])
== [-1, 3, 7, 8, 9, 10, 50, 60]