Why is this algorithm stable and how could I make it unstable?

Question

I'm asking because of interest, need to somehow understand how to know if an algorithm is stable or not.

What means stable? A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted.

If I understood the algorithm correctly, equal elements of the array cannot be assigned to the same array, so it is a stable algorithm.

How could I make this unstable? I don't want to do great changes, what about changing for i = n down to 1 do to for i = 1 to n do? I think this should be one way of breaking it but I'm not quite sure :D

Input: Array arr with n integers, from 1 to m
Output: Array arr sorted upwards

Initialize Array B with length m which is set to 0 everywhere
n <-- |arr|
Initialize Array C with length n
for i = 1 to n do
   B[arr[i] <-- B[arr[i]] + 1
end for
for j = 2 to m do
   B[j] <-- B[j] + B[j-1]
end for
for i = n down to 1 do
   C[B[arr[i]]] <-- arr[i]
   B[arr[i]] <-- B[arr[i]] - 1
end for
return C

This should be the same as above code:

countingsort(A, k)
{
  C = array(0, k)
  for (m=0; m<=k; m=m+1)
    C[m] = 0
  // end for
  for (j=1; j<=A.size; j=j+1)
    C[A[j]] = C[A[j]] + 1
  // end for
  i=0
  B = array(1, A.size)
  for (m=0; m<=k; m=m+1)
    while ( C[m]>0 )
    { 
      B[i] = m
      i = i+1
      C[m]=C[m]-1
    } // end while
  // end for
  return B
}

Hi again, you are not sorting... so there is no need to say stable or not... — Thomas
– Thomas, Commented Jun 12, 2016 at 19:59
There are existing programming languages which show the algorithm much clearer than this hypothetical language. Just saying... What I try to say in fact is: Why let us guess what this "code" actually does, instead of giving the name of the sorting algorithm you have in mind? Or alternatively give us code we can execute to see if it is even sorting? — BitTickler
– BitTickler, Commented Jun 12, 2016 at 20:01
I don't know myself how this is called, but we call it "Linearsort", probably because it sorts in linear time...? I think a more general name for this algorithm would be counting sort. — itaminul
– itaminul, Commented Jun 12, 2016 at 20:08
For an explanation of what stability means, see stackoverflow.com/a/8312128/56778 — Jim Mischel
– Jim Mischel, Commented Jun 13, 2016 at 13:53

rcgldr · Accepted Answer · 2016-06-12 20:50:28Z

1

It's a counting / radix sort with a single field that sorts the array going from n to 1. Switching the last for loop to be 1 to n would make it unstable, as equal elements would be stored in reverse order.

edited Jun 12, 2016 at 20:50

answered Jun 12, 2016 at 20:10

rcgldr

29.4k3 gold badges41 silver badges70 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Why is this algorithm stable and how could I make it unstable?

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related