CODEWITHSUNDEEP
pythonsorting
user2172370
user2172370

Reputation:

Recursive Insertion Sort in python

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)

Upvotes: 2

Views: 3795

Answers (1)

Anindya Guha
Anindya Guha

Reputation: 150

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.

Upvotes: 2

Related Questions