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

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

### #1

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

Posted 22 August 2016 - 09:21 AM

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

### #2

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

### #3

## 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?

### #4

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

Posted 22 August 2016 - 05:22 PM

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

### #5

## 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 3

By hand, use insertion sort on this example. Keep track of each instance of 3. What happens when you hit 3

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

_{A}5 3_{B}3_{C}.By hand, use insertion sort on this example. Keep track of each instance of 3. What happens when you hit 3

_{B}? Do you ever move it before 3_{A}? Justify using the steps of the algorithm.From this example, try to generalize for an arbitrary array.

### #6

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

Posted 23 August 2016 - 09:25 AM

jsvillatech, 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?

### #7

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

Posted 23 August 2016 - 03:53 PM

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

jsvillatech, 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

macosxnerd101, 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 3

By hand, use insertion sort on this example. Keep track of each instance of 3. What happens when you hit 3

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

_{A}5 3_{B}3_{C}.By hand, use insertion sort on this example. Keep track of each instance of 3. What happens when you hit 3

_{B}? Do you ever move it before 3_{A}? 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

### #8

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

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.

Page 1 of 1