Recursive Insertion Sort in python

Question

I am trying to write iterative and recursive versions of all the sorting algorithms in python. Other than the fact that I am not returning anything, what is wrong with this? Is it a problem with my slicing?

Attempt at solution:

    def insertOne(element, aList):
    ''' Inserts element into its proper place in a sorted list aList.
        input: element is an item to be inserted.  aList is a sorted list.
        output: A sorted list.
    '''
    if len(aList) == 0:
        return [element]
    elif element < aList[0]:
        return [element] + aList
    else:
        return aList[0:1] + insertOne(element, aList[1:])





    def sort(aList):

    if len(aList) == 0:
        return []

    n = len(aList)
    if n > 1:
        sort(aList[:n - 1])
        insertOne(n, aList)




     aList = [3,2,1]

     print sort(aList)

The first thing wrong would be your indentation. Python uses indentation to determine the bounds of multi-line statements like if and for; this code will fail on line 1 with an IndentationError. — user2357112
– user2357112, Commented Aug 6, 2013 at 1:54
The second problem is that you're mixing up in-place operations and things that return new lists. aList[:n - 1] is a new, independent list constructed from aList; sorting it won't affect aList at all. Similarly, returning something from insertOne won't affect the value of aList. — user2357112
– user2357112, Commented Aug 6, 2013 at 1:56
The third problem would be that insertOne is supposed to take an element to insert and a sorted sublist to insert into, but insertOne(n, aList) passes an index and a partially sorted list that already contains the element you want to insert. — user2357112
– user2357112, Commented Aug 6, 2013 at 1:59

Anindya Guha · Accepted Answer · 2013-08-06 02:21:06Z

2

Your sort method is wrong. n is the length of aList, not an element. You wouldn't want to put it in the list, which is what you're doing with insertOne(n, aList).

What you want to do is this:

def sort(aList):
  if len(aList)<=1:
    return aList
  else:
    return insertOne(aList[0], sort(aList[1:]))

Basically, you're going through aList, and inserting every element you encounter in its correct position using insertOne.

answered Aug 6, 2013 at 2:21

Anindya Guha

1501 gold badge1 silver badge8 bronze badges

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

Collectives™ on Stack Overflow

Recursive Insertion Sort in python

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related