CODEWITHSUNDEEP
pythonsortingpython-3.xrecursion
Steve
Steve

Reputation: 61

Recursive Selection sort to return a descending list in python

I'd been working through a problem, to sort the elements in a descending order through a recursive approach, the code is as follows..

import operator

def do_stuff(elem_list):

    if not elem_list:
        return None

    max_index , max_element = max(enumerate(elem_list) , key = operator.itemgetter(1))
    elem_list[max_index],elem_list[0] = elem_list[0],elem_list[max_index]

    return do_stuff(elem_list[1:])

p_list = [4,2,3,5,1]
do_stuff(p_list)
print(p_list)

Output - 

[5, 2, 3, 4, 1]

And I can't seem to figure wherein lies the problem and why won't I get the desired output ?

Upvotes: 1

Views: 1182

Answers (2)

WilliamComputerScience
WilliamComputerScience

Reputation: 87

I was able to fix your problem by adding an extra parameter, since you seem to be using a recursive implementation of insertion sort, you need some way to track the next open place to swap values in the list. 

import operator
def sortl(l, last):
    # base case
    if last + 1 >= len(l):
         return l
    # find the max index (mi) and max value in the list
    mi, _ = max(enumerate(l[last:]), key = operator.itemgetter(1))
    mi += last # caculate the offset in the sublist
    l[mi], l[last] = l[last], l[mi] # swap the values

    # recursive call
    return sortl(l, last + 1)

By using "last + 1" every time, you are able to simulate using the underlying sublist since calling do_stuff([some_list[1:]) wont work

Upvotes: 1

szym
szym

Reputation: 5846

Python's slices are not true references to the underlying list. See: Can I create a "view" on a Python list?

Upvotes: 0

Related Questions