7 Replies - 996 Views - Last Post: 24 August 2016 - 06:18 PM

#1 jsvillatech  Icon User is offline

  • New D.I.C Head

Reputation: 4
  • View blog
  • Posts: 17
  • Joined: 14-March 15

How do I know if a certain sorting algorithm is stable?

Posted 22 August 2016 - 09:21 AM

Hello, I was given a bunch of algorithms to analyze and determine if they are stable or not.
I know that that an algorithm is stable if two objects with equal keys appear in the same order in sorted output as they appear in the input unsorted array.
But I don't know how to determine that when it comes to code. what criteria should I use?

Thanks
Is This A Good Question/Topic? 0
  • +

Replies To: How do I know if a certain sorting algorithm is stable?

#2 jon.kiparsky  Icon User is offline

  • Screw Trump (before he screws you)
  • member icon


Reputation: 10625
  • View blog
  • Posts: 18,185
  • Joined: 19-March 11

Re: How do I know if a certain sorting algorithm is stable?

Posted 22 August 2016 - 01:02 PM

Interesting question. I think I'm going to move it to Computer Science, since it's not language-specific.
Was This Post Helpful? 0
  • +
  • -

#3 jon.kiparsky  Icon User is offline

  • Screw Trump (before he screws you)
  • member icon


Reputation: 10625
  • View blog
  • Posts: 18,185
  • Joined: 19-March 11

Re: How do I know if a certain sorting algorithm is stable?

Posted 22 August 2016 - 01:08 PM

So let's start by thinking this through. What would have to be true about a sorting algorithm for it to be stable? Or, thinking about it from the other end, what characteristics or behaviors would you look for to see if an algorithm is not stable?
Was This Post Helpful? 0
  • +
  • -

#4 jsvillatech  Icon User is offline

  • New D.I.C Head

Reputation: 4
  • View blog
  • Posts: 17
  • Joined: 14-March 15

Re: How do I know if a certain sorting algorithm is stable?

Posted 22 August 2016 - 05:22 PM

View Postjon.kiparsky, on 22 August 2016 - 01:08 PM, said:

So let's start by thinking this through. What would have to be true about a sorting algorithm for it to be stable? Or, thinking about it from the other end, what characteristics or behaviors would you look for to see if an algorithm is not stable?

Thanks for answering :). What I understand about an algorithm in order to be stable is, for example, we have a deck of cards and if there are elements that are equal, the algorithm respects the order. but what I don't really understand is when we have an int array and there is a sequence of numbers 2 4 3 5 3 3. how do I know if those 3 swapped positions?
Thanks in advance
Was This Post Helpful? 1
  • +
  • -

#5 macosxnerd101  Icon User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12135
  • View blog
  • Posts: 45,119
  • Joined: 27-December 08

Re: How do I know if a certain sorting algorithm is stable?

Posted 22 August 2016 - 05:42 PM

Let's take insertion sort for example. And consider your sequence 2 4 3 5 3 3. Now we label each 3 for our purposes, just to keep track of them (the algorithms do no such thing, but we do for the sake of the proof- and this is a good proof strategy for proving a sorting algorithm is stable): 2 4 3A 5 3B 3C.

By hand, use insertion sort on this example. Keep track of each instance of 3. What happens when you hit 3B? Do you ever move it before 3A? Justify using the steps of the algorithm.

From this example, try to generalize for an arbitrary array.
Was This Post Helpful? 1
  • +
  • -

#6 jon.kiparsky  Icon User is offline

  • Screw Trump (before he screws you)
  • member icon


Reputation: 10625
  • View blog
  • Posts: 18,185
  • Joined: 19-March 11

Re: How do I know if a certain sorting algorithm is stable?

Posted 23 August 2016 - 09:25 AM

View Postjsvillatech, on 22 August 2016 - 07:22 PM, said:

Thanks for answering :)/>. What I understand about an algorithm in order to be stable is, for example, we have a deck of cards and if there are elements that are equal, the algorithm respects the order. but what I don't really understand is when we have an int array and there is a sequence of numbers 2 4 3 5 3 3. how do I know if those 3 swapped positions?


That's something that's true about the result - if the algorithm is stable, then the result has certain qualities, specifically, order is preserved for identically-sorting elements. What you want to ask yourself is, what has to be true about the algorithm for this to be the case, in general?

So for example, let's imagine an algorithm called RandomSort. This operates by pulling a randomly-selected element e from the list to be sorted (removing it from the list) and walking up a list of sorted output until it reaches an element which sorts after or equal to e. e is inserted before that element.

Leaving any concerns about the complexity of this algorithm (you might enjoy thinking about why it sucks, but that's another question), I think it's pretty clear that RandomSort is NOT stable. Why? What does it do that makes it clearly not stable?
Was This Post Helpful? 0
  • +
  • -

#7 jsvillatech  Icon User is offline

  • New D.I.C Head

Reputation: 4
  • View blog
  • Posts: 17
  • Joined: 14-March 15

Re: How do I know if a certain sorting algorithm is stable?

Posted 23 August 2016 - 03:53 PM

View Postjon.kiparsky, on 23 August 2016 - 09:25 AM, said:

View Postjsvillatech, on 22 August 2016 - 07:22 PM, said:

Thanks for answering :)/>/>. What I understand about an algorithm in order to be stable is, for example, we have a deck of cards and if there are elements that are equal, the algorithm respects the order. but what I don't really understand is when we have an int array and there is a sequence of numbers 2 4 3 5 3 3. how do I know if those 3 swapped positions?


That's something that's true about the result - if the algorithm is stable, then the result has certain qualities, specifically, order is preserved for identically-sorting elements. What you want to ask yourself is, what has to be true about the algorithm for this to be the case, in general?

So for example, let's imagine an algorithm called RandomSort. This operates by pulling a randomly-selected element e from the list to be sorted (removing it from the list) and walking up a list of sorted output until it reaches an element which sorts after or equal to e. e is inserted before that element.

Leaving any concerns about the complexity of this algorithm (you might enjoy thinking about why it sucks, but that's another question), I think it's pretty clear that RandomSort is NOT stable. Why? What does it do that makes it clearly not stable?


Now I understand thank you! yeah random sort doesn't respect the order at all. while bubble and others do that

View Postmacosxnerd101, on 22 August 2016 - 05:42 PM, said:

Let's take insertion sort for example. And consider your sequence 2 4 3 5 3 3. Now we label each 3 for our purposes, just to keep track of them (the algorithms do no such thing, but we do for the sake of the proof- and this is a good proof strategy for proving a sorting algorithm is stable): 2 4 3A 5 3B 3C.

By hand, use insertion sort on this example. Keep track of each instance of 3. What happens when you hit 3B? Do you ever move it before 3A? Justify using the steps of the algorithm.

From this example, try to generalize for an arbitrary array.



Thank you so much, that was really helpful, now I understand the concept :)
Was This Post Helpful? 0
  • +
  • -

#8 ishkabible  Icon User is offline

  • spelling expret
  • member icon





Reputation: 1739
  • View blog
  • Posts: 5,895
  • Joined: 03-August 09

Re: How do I know if a certain sorting algorithm is stable?

Posted 24 August 2016 - 06:18 PM

I like thinking about this in terms of a lexicographic ordering.

Say there was some ordering on the list to begin with and it was sorted, call this ordering P. A stable sort is a sort that if sorted a P-sorted list with ordering Q would produce a (Q, P)-sorted (where "(Q, P)" is the lexicographic product of Q and P) list. So the question to ask is "does this sort produce a (Q, P)-sorted list?". If the answer is "yes" you have a stable sort. What does it mean for a list to be (Q, P) sorted? It means that within subranges of equal Q-sorted lists those sub lists are P-sorted. You can think of P as being the index in the original array. This gives rise to a way to *make* a non-stable sort stable.

First copy the list into an ordered map (using Q as the ordering as any ordering will do and you have Q on hand) so that items are mapped to their index. Next Q-sort that list. Next for each Q-equal subsequence sort that subsequence by using the original index as the ordering. You now, in linear memory, have produced a stable sorting algorithm that runs in O(n*lg(n))!

Another note I like to make is that you can implement quick sort stably if you have extra memory.

pick your pivot. scan though your list putting elements less than the pivot in one part and greater than it and the back part (reversed). reverse the back partition so it's in the correct order (or be clever and do this at the end only if it is needed by passing different orderings). now sort each of these recursively.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1