How can I implement insertion sort using recursion and which is more efficient?

Question

How could I implement this using recursion, and would it be more effcient?

My code:

def insertionSort(array):
    '''(list) - > list
    Returns a sorted list of integers by implementing
    the insertion sort which returns numbers in array from
    least to greatest
    '''
    for i in range(1, len(array)):

        if array[i-1] > array[i]: #Finds a number out of place
            temp = array[i]
            for a in range(0,i):
                if temp < array[a]:
                    array.insert(a,temp)
                    del array[i+1]
                    break
    return array

No it isn't more efficient to use recursion, it is usually much more costly, also have you attempted implementing recursion yourself? — jamylak
– jamylak, Commented Mar 23, 2013 at 5:45
@jamylak Doesnt Python optimize recursion, and that too by quite a bit ? I have seen some posts here on SO with time measurements that would suggest almost equivalent performance from both recursion and iteration. — asheeshr
– asheeshr, Commented Mar 23, 2013 at 5:48
@AshRj Which posts are you talking about? Python recursion is notably slow — jamylak
– jamylak, Commented Mar 23, 2013 at 5:49

perreal · Accepted Answer · 2013-03-23 06:32:20Z

4

A simple recursive version:

def insertionSort(array,i=1):
  if i >= len(array):
    return array
  if array[i-1] > array[i]: 
    temp = array[i]
    for a in range(0, i): 
      if temp < array[a]:
        array.insert(a,temp)
        del array[i+1]
        break
  return insertionSort(array, i+1)

Generally recursion is better for certain data structures such as trees and linked lists. Sometimes it is easier to think in terms of recursion to solve a problem. I don't remember a case where recursion actually used for efficiency.

answered Mar 23, 2013 at 6:32

perreal

98.7k23 gold badges159 silver badges187 bronze badges

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

Comments

Gene · Accepted Answer · 2013-03-23 06:21:37Z

0

Any for loop for x in range(a,b): Body can be reimplemented with tail recursion:

def rfor(b, x = a):
  if a < b:
     Body
     rfor(b, x + 1)

This ought to give you enough to get the answer yourself. In standard Python this will definitely be slower than the loop and eat one stack frame per iteration. In other languages and implementations with good tail call optimization, they'll be equal in cost. Apparently Guido has said he's uninterested in tail call optimization.

edited Mar 23, 2013 at 6:21

answered Mar 23, 2013 at 6:11

Gene

47.1k4 gold badges64 silver badges101 bronze badges

Collectives™ on Stack Overflow

How can I implement insertion sort using recursion and which is more efficient?

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related