mercredi 13 mai 2015

Is counting sort in place & stable or not?

As the question says , I want to confirm whether counting sort algorithm is in-place sorting algorithm or not.

Wikipedia describes in-place algorithm as

In computer science, an in-place algorithm (or in Latin in situ) is an algorithm which transforms input using a data structure with a small, constant amount of extra storage space. The input is usually overwritten by the output as the algorithm executes. An algorithm which is not in-place is sometimes called not-in-place or out-of-place (or ex situ in Latin).

Stable sorting algorithms maintain the relative order of records with equal keys (i.e. values). That is, a sorting algorithm is stable if whenever there are two records R and S with the same key and with R appearing before S in the original list, R will appear before S in the sorted list.

and also somewhere below counting sort page :

As described, counting sort is not an in-place algorithm; even disregarding the count array, it needs separate input and output arrays.

if we assume counting sort algorithm as :

countsort(){
    for i = 0 .... n  //where n is size of input array arr[]
        countArr[ arr[i] ] += 1
    //and then traverse countArr[] and rewrite arr[] with sorted values where value>0

then how come is this not a stable and in place sort?

Lets say input key data is represented by numerals and satellite data by characters , then for following data:

arr[] = { 1a,1b,1c,2z,5c,6c,7e,8q }  // keeping in mind only keys are sorted

wouldn't this algo traverse 1a then 1b then 1c and rewrite them in that very order? And also same array is being overwritten , so we just need a constant space depending upon type of keys rather than number of keys.

Thanks.

Aucun commentaire:

Enregistrer un commentaire