-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.

$\endgroup$
3
  • $\begingroup$ Please reproduce the problem statement as in your homework. An O(n) general sort is not possible. $\endgroup$
    – user16034
    Commented Apr 18, 2023 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
    Commented Apr 18, 2023 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$ Commented Apr 18, 2023 at 22:08

1 Answer 1

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.

$\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$ Commented Apr 18, 2023 at 22:22
  • $\begingroup$ @user19843013: you are close. $\endgroup$
    – user16034
    Commented Apr 19, 2023 at 7:54
  • $\begingroup$ Which guess was close, the key index pairs or duplicating the whole list? $\endgroup$ Commented Apr 19, 2023 at 8:14
  • $\begingroup$ @user19843013: sorry, I am not going to ease your task. $\endgroup$
    – user16034
    Commented Apr 19, 2023 at 8:15

Your Answer

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

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