0

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
}
itaminul
  • 53
  • 5
  • 2
    Hi again, you are not sorting... so there is no need to say stable or not... – Thomas Jun 12 '16 at 19:59
  • 1
    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 Jun 12 '16 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 Jun 12 '16 at 20:08
  • 1
    For an explanation of what stability means, see http://stackoverflow.com/a/8312128/56778 – Jim Mischel Jun 13 '16 at 13:53

1 Answers1

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.

rcgldr
  • 27,407
  • 3
  • 36
  • 61