I have to sort an array using insertion sort and using recursion (without loops)

Question

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?

Your code is suspicious - you pass a parameter j, but it is never used (you immediately overwrite its value with j = i - 1) — Stef
– Stef, Commented Dec 13, 2021 at 15:41
Could you please explain the logic behind your code? Currently, you are showing us a code that doesn't work, and you expect us to understand what it was supposed to do and how to fix it so it does it correctly. Since it doesn't actually do what you want, we can't guess what you wanted to do. Please add english sentences to explain what i and j are, and what is the logic, and how this was supposed to be an implementation of insertion sort (for instance, where is the actual insertion happening?) — Stef
– Stef, Commented Dec 13, 2021 at 15:43

Raaghavi · Accepted Answer · 2024-05-30 12:42:40Z

1

This one works for me,

def insertionSort(a, index):
    if index == len(a):
        return a
    else:
        if index > 0:
            for i in range(index, len(a)):
                temp = a[i]
                j = i - 1
                while j>=0 and a[j] > temp:
                    a[j+1] = a[j]
                    j -= 1
                a[j+1] = temp
        return insertionSort(a, index+1)

print(insertionSort([10, 8, 7, 50, 60, 3, 9, -1], 0))

edited May 30, 2024 at 12:42

answered May 30, 2024 at 12:39

Raaghavi

263 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Mulan · Accepted Answer · 2021-12-13 15:59:07Z

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 the dst array
(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 -

If the input t is empty, the only possible output is [x]
(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)
(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]

Erik McKelvey · Accepted Answer · 2021-12-13 15:50:51Z

0

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]

answered Dec 13, 2021 at 15:50

Erik McKelvey

1,6372 gold badges17 silver badges25 bronze badges

Collectives™ on Stack Overflow

I have to sort an array using insertion sort and using recursion (without loops)

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related