Recursive Selection sort to return a descending list in python

Question

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 ?

elem_list[1:] is a completely separate list from elem_list. — user2357112
– user2357112, Commented May 4, 2016 at 18:15
It is but a slice of the elem_list. After the function, upon printing the list again, should it not give me the correct stuff ? — Steve
– Steve, Commented May 4, 2016 at 18:29
Try fiddling with l1 = [1, 2, 3]; l2 = l1[1:] in interactive mode and see what effect changing one list has on the other. — user2357112
– user2357112, Commented May 4, 2016 at 18:31

WilliamComputerScience · Accepted Answer · 2016-05-04 18:54:24Z

1

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

answered May 4, 2016 at 18:54

WilliamComputerScience

875 bronze badges

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

2 Comments

Steve Over a year ago

Thanks a lot. That does it perfectly !!

Blckknght Over a year ago

You can give last a default value of 0, so that you can call sortl with just a list and it will still work as expected.

Community · Accepted Answer · 2017-05-23 11:59:39Z

0

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

edited May 23, 2017 at 11:59

CommunityBot

11 silver badge

answered May 4, 2016 at 18:38

szym

5,90630 silver badges35 bronze badges

Collectives™ on Stack Overflow

Recursive Selection sort to return a descending list in python

2 Answers 2

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related