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