CODEWITHSUNDEEP
pythonlistrecursion
user3002302
user3002302

Reputation: 25

recursive sorting in python

I am trying to run a sorting function recursively in python. I have an empty list that starts everything but everytime I try to print the list I get an empty list. here is my code. Any help would be greatly appreciated

def parse(list):
    newParse = []
    if len(list) == 0:
        return newParse
    else:

        x = min(list)

        list.remove(x)
        newParse.append(x)

        return sort(list)

Upvotes: 2

Views: 9441

Answers (2)

rlms
rlms

Reputation: 11060

Here is what I think you are trying to do:

def recursive_sort(a_list):
    def helper_function(list_to_be_sorted, list_already_sorted):
        new = []
        if len(list_to_be_sorted) == 0:
            return list_already_sorted
        else:    
            x = min(list_to_be_sorted)    
            list_to_be_sorted.remove(x)
            new.append(x)
            return helper_function(list_to_be_sorted, list_already_sorted + new)
    return helper_function(a_list, [])

You shouldn't name variables list, as that is a builtin.

Also, if you are trying to implement a recursive sort function, you might want to look at quicksort, which is a very common (and fast) recursive sorting algorithm. What you have tried to implement is a recursive version of selection sort, which is much slower.

Also, if you actually need a sorting function, rather than just wanting to implement a recursive one, you should use the list method sort, or the function on an iterable sorted, both of which will be a lot faster than anything you could make in Python.

Upvotes: 0

muhmuhten
muhmuhten

Reputation: 3341

The value of newParse is not preserved between invocations of the function; you're setting it equal to [] (well, you're creating a new variable with the value []).

Since the only time you return is

newParse = []
if len(list) == 0:
    return newParse`

you will always be returning [] because that is the value of newParse at that time.

Because you are doing this recursively, you are calling the function anew, without keeping the function's own state. Take a moment to consider the implications of this on your code.

Instead of initialising newParse = [], add an optional parameter newParse defaulting to a bogus value, and set newParse = [] if you receive that bogus value for newParse. Otherwise, you'll actually be getting the same list every time (i.e. the contents of the list object are being mutated). And newParse through in your tail call.

You also seem to have the problem that your definition and and the supposedly-recursive call refer to different functions.

def sort(list, newParse = None):
    if newParse is None:
        newParse = []
    if len(list) == 0:
        return newParse
    else:
        x = min(list)
        list.remove(x)
        newParse.append(x)
        return sort(list, newParse)

Upvotes: 3

Related Questions