Сортирање пребројавањем

У информатици, сортирање пребројавањем (counting sort) представља алгоритам за сортирање помоћу целих бројева, тј. алгоритам целобројног сортирања. Алгоритам ради тако што пребројава колико се пута сваки елемент низа јавља и на основу тога одређује позицију сваког елемента у излазном низу. Временска сложеност алгоритма је линеарна и зависи од броја вредности које се сортирају и разлике највеће и најмање вредности. Због тога је овај алгоритам погодан за сортирање низова код којих разлика између највеће и најмање вредности није значајно већа од укупног броја елемената. Сортирање пребројавањем се користи као део радикс сортирања који много ефикасније сортира велике вредности.^[1][2][3]

Пошто алгоритам користи вредности елемената низа као индексе за помоћни низ, не подлеже ограничењу које имају алгоритми поређења, да је сложеност у најгорем случају О(n logn) . Радикс сортирања се може искористити за сличне проблеме као и сортирање пребројавањем; међутим за сегментно сортирање су потребне повезане листе, динамички низови или велика количина унапред алоциране меморије за чување елемената у сваком сегменту. За разлику од сегментног сортирања, сортирање пребројавањем користи један број за сваки сегмент.

Улаз и Излаз

У већини случајева, улаз у алгоритам је n елемената, где сваки елемент представља ненегативан цео број чија вредност није већа од k.^[3] У неким дефиницијама улаз се наводи као низ целих бројева,^[1] али ово поједностављење не одговара многим применама овог алгоритма. На пример када се користи као део радикс сортирања улаз представљају појединачне цифре бројева који се сортирају.

У већини случајева када се овај алгоритам примењује, нпр. радикс сортирање, максимална вредност елемента mvar|k је унапред позната, и као таква представља део улазних вредности. У случају да mvar|k није познато, може се прерачунати увођењем додатне петље која одређује максималну вредност елемената.

Излаз је сортирани низ елемената. Због примене код радикс сортирања веома је важно да сортирање пребројавањем буде стабилан; у случају када два елемента имају исти кључ, требало би да имају исти поредак у излазном као и у улазном низу.^[1][2]

Алгоритам

Нека је дато n елемената, који представљају целе бројеве из опсега од 1 до m, m≥n. Резервише се m локација, а онда се за свако i број xi ставља на локацију xi која одговара његовој вредности. После тога се редом прегледају све локације и из њих се покупе елементи. Сложеност овог алгоритма је O(m + n).^[4]

Имплементација у C коду:

#include<stdio.h>
main(){
  int i,j,k,n;
  int a[100],b[100],c[100];
  scanf("%d%d",&n,&k);

  for (i=0;i<n;i++)
       scanf("%d",&a[i]);

  for (i=0;i<k;i++)
       c[i]=0;

  for (j=0;j<n;j++)
       c[a[j]]=c[a[j]]+1;

  for (i=1;i<k;i++)
       c[i]=c[i]+c[i-1];

  for (j=n-1;j>=0;j--){
       b[c[a[j]]]=a[j];
       c[a[j]]=c[a[j]]-1;
  }

  for (i=0;i<n;i++)
       printf("%d ",b[i]);
}

Модификована верзија

Одређује се најмања и највећа вредност улазног низа a. Број појављивања чланова низа a памти се у помоћном низу o проласком кроз елементе низа у интервалу од најмањег до највећег.^[4]

Имплементација у C++ коду:

#include<stdio.h>
#include<limits.h>
#define MAX 200

main(){
  int i,j,n,min,max,k;
  int a[MAX],o[4*MAX];

  scanf("%d",&n);

  min=INT _MAX;
  max=0;
  k=0;

  for (j=0;j<=4*MAX;j++)
        o[j]=0;

  for(i=1;i<=n;i++){
        scanf("%d",&a[i]);
        o[a[i]]+=1;
        
        if (a[i]>max) max=a[i];
               if (a[i]<min)
                      min=a[i];
  }

  for (i=min;i<=max;i++)
        if (o[i]!=0)
               for (j=1;j<=o[i];j++){
                      k=k+1;
                      a[k]=i;
  }

  for (i=1;i<=n;i++)
        printf("%d ",a[i]);

}

Варијације алгоритма

За податке у којима је максимална величина кључа знатно мања од броја елемената, алгоритам може бити паралелизован раздвајањем улаза у приближно једнаке поднизове, паралелним обрађивањем сваког подниза и генерисањем одвојеног низа појављивања елемената за сваки подниз, и коначно спајањем низова појављивања. Када се користи као део паралелног алгоритма радикс сортирања, величина кључа би требало да одговара величини подељених поднизова.^[5] Једноставност алгоритма пребројавањем и лака паралелизација га чине употребљивим у паралелним алгоритмима финије структуре.^[6]

Као што је описано, алгоритам сортирања пребојавањем није аlgoritam za sortiranje u mestu; чак иако се занемари низ појављивања, потребни су му одвојени улазни и излазни низови. Модификација у којој се елементи чувају сортирани у истом низи који је дат на улазу је могућа, приказана раније; међутим при таквој модификацији алгоритам губи стабилност.^[3]