-2
$\begingroup$

The stable algorithm has to run in O(n) time and must call the following unstable algorithm at least once.

EDIT: Calling unstablesort() is free (costs 0 operations).

def unstablesort(l):
    return selectionsort(shuffled(l)) # shuffled(l) returns list l randomized

This is apparently an easy question but frankly I don't know where to start.

Improve this question
$\endgroup$
3
  • $\begingroup$ Please reproduce the problem statement as in your homework. An O(n) general sort is not possible. $\endgroup$
    – user16034
    Apr 18 at 6:20
  • $\begingroup$ Question 1: In which situation does it not matter that the unstable sort is unstable? Question 2: How can you create this situation? $\endgroup$
    – gnasher729
    Apr 18 at 13:46
  • $\begingroup$ @gnasher729 When there are no duplicates, I can create that by looping through the list and creating a set but then I don't see how to go about adding the duplicates back in and keeping it O(n). For example if all the items are equal $\endgroup$
    – user19843013
    Apr 18 at 22:08

1 Answer 1

Reset to default
2
$\begingroup$

Hint:

Unstable sorting shuffles the data in an unrecoverable way (because identical keys are... identical), so you must somehow save the initial position information.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Make a list of key : index pairs? Or duplicate the whole list, sort one and compare the two somehow? I'm not seeing a way to make it work $\endgroup$
    – user19843013
    Apr 18 at 22:22
  • $\begingroup$ @user19843013: you are close. $\endgroup$
    – user16034
    Apr 19 at 7:54
  • $\begingroup$ Which guess was close, the key index pairs or duplicating the whole list? $\endgroup$
    – user19843013
    Apr 19 at 8:14
  • $\begingroup$ @user19843013: sorry, I am not going to ease your task. $\endgroup$
    – user16034
    Apr 19 at 8:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.