CODEWITHSUNDEEP
sortingquicksort
Paradox
Paradox

Reputation: 353

Quicksort - conditions that makes it stable

A sorting algorithm is stable if it preserves the relative order of any two elements with equals keys. Under which conditions is quicksort stable?

Quicksort is stable when no item is passed unless it has a smaller key.

What other conditions make it stable?

Upvotes: 10

Views: 30902

Answers (3)

W.Perrin
W.Perrin

Reputation: 4725

The condition is easy to figure out, just keep the raw order for equal elements. There is no other condition that has essential differences from this one. The point is how to achieve it.

There is a good example.

1. Use the middle element as the pivot.

2. Create two lists, one for smaller, the other for larger.

3. Iterate from the first to the last and put elements into the two lists. Append the element smaller than or equals to and ahead of the pivot to the smaller list, the element larger than or equals to and behind of the pivot to the larger list. Go ahead and recursive the smaller list and the larger list.

https://www.geeksforgeeks.org/stable-quicksort/

The latter 2 points are both necessary. The middle element as the pivot is optional. If you choose the last element as pivot, just append all equal elements to the smaller list one by one from the beginning and they will keep the raw order in nature.

Upvotes: 5

user684934
user684934

Reputation:

You can add these to a list, if that's your approach:

  • When the elements have absolute ordering
  • When the implementation takes O(N) time to note the relative orderings and restores them after the sort
  • When the pivot chosen is ensured to be of a unique key, or the first occurence in the current sublist.

Upvotes: 0

Justin Peel
Justin Peel

Reputation: 47082

Well, it is quite easy to make a stable quicksort that uses O(N) space rather than the O(log N) that an in-place, unstable implementation uses. Of course, a quicksort that uses O(N) space doesn't have to be stable, but it can be made to be so.

I've read that it is possible to make an in-place quicksort that uses O(log N) memory, but it ends up being significantly slower (and the details of the implementation are kind of beastly).

Of course, you can always just go through the array being sorted and add an extra key that is its place in the original array. Then the quicksort will be stable and you just go through and remove the extra key at the end.

Upvotes: 16

Related Questions