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 = [] -

1. If src is empty, there is nothing left to sort. Return the dst array
2. (inductive) src has at least one element. insert the first element src[0] into dst and recur on the sub-problem src[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 -

1. If the input t is empty, the only possible output is [x]
2. (inductive) t has at least one element. If the first element t[0] is less than the element to insert x, then prepend t[0] to the result of the recursive sub-problem insert(t[1:], x)
3. (inductive) t the first element is greater than or equal to x. Prepend x to t

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]