CODEWITHSUNDEEP
arraysalgorithmsorting
itaminul
itaminul

Reputation: 53

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

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
}

Upvotes: 0

Views: 454

Answers (1)

rcgldr
rcgldr

Reputation: 28818

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.

Upvotes: 1

Related Questions