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

У информатици, сортирање пребројавањем (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]

Референце

^ ^а ^б ^в Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), „8.2 Counting Sort”, Introduction to Algorithms (2nd изд.), MIT Press and McGraw-Hill, стр. 168—170, ISBN 0-262-03293-7 . See also the historical notes on page 181.
^ ^а ^б Edmonds, Jeff (2008), „5.2 Counting Sort (a Stable Sort)”, How to Think about Algorithms, Cambridge University Press, стр. 72—75, ISBN 978-0-521-84931-9 .
^ ^а ^б ^в Sedgewick, Robert (2003), „6.10 Key-Indexed Counting”, Algorithms in Java, Parts 1-4: Fundamentals, Data Structures, Sorting, and Searching (3rd изд.), Addison-Wesley, стр. 312—314 .
^ ^а ^б Преузето из предавања "Конструкција и анализа алгоритама 2", Јелене Hadži-Purić. Математички факултет, Универзитет у Београду
^ Zagha, Marco; Blelloch, Guy E. (1991), „Radix sort for vector multiprocessors”, Proceedings of Supercomputing '91, November 18-22, 1991, Albuquerque, NM, USA, IEEE Computer Society / ACM, стр. 712—721, doi:10.1145/125826.126164 .
^ Reif, John H. (1985), „An optimal parallel algorithm for integer sorting”, Proc. 26th Annual Symposium on Foundations of Computer Science (FOCS 1985), стр. 496—504, doi:10.1109/SFCS.1985.9 .

Спољашње везе

Counting Sort html5 visualization
Demonstration applet from Cardiff University Архивирано на сајту Wayback Machine (2. јун 2013)
Efficient Counting Sort in Haskell Архивирано на сајту Wayback Machine (3. април 2012)
Kagel, Art S. (2. 6. 2006), „counting sort”, Ур.: Black, Paul E., Dictionary of Algorithms and Data Structures, U.S. National Institute of Standards and Technology, Приступљено 21. 4. 2011 .
A simple Counting Sort implementation.
Конструкција и анализа алгоритама 2", Јелене Hadži-Purić. Математички факултет, Универзитет у Београду

[clrs-1] а ^б ^в Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), „8.2 Counting Sort”, Introduction to Algorithms (2nd изд.), MIT Press and McGraw-Hill, стр. 168—170, ISBN 0-262-03293-7 . See also the historical notes on page 181.

[edmonds-2] а ^б Edmonds, Jeff (2008), „5.2 Counting Sort (a Stable Sort)”, How to Think about Algorithms, Cambridge University Press, стр. 72—75, ISBN 978-0-521-84931-9 .

[sedgewick-3] а ^б ^в Sedgewick, Robert (2003), „6.10 Key-Indexed Counting”, Algorithms in Java, Parts 1-4: Fundamentals, Data Structures, Sorting, and Searching (3rd изд.), Addison-Wesley, стр. 312—314 .

[autogenerated1-4] а ^б Преузето из предавања "Конструкција и анализа алгоритама 2", Јелене Hadži-Purić. Математички факултет, Универзитет у Београду

[5] Zagha, Marco; Blelloch, Guy E. (1991), „Radix sort for vector multiprocessors”, Proceedings of Supercomputing '91, November 18-22, 1991, Albuquerque, NM, USA, IEEE Computer Society / ACM, стр. 712—721, doi:10.1145/125826.126164 .

[6] Reif, John H. (1985), „An optimal parallel algorithm for integer sorting”, Proc. 26th Annual Symposium on Foundations of Computer Science (FOCS 1985), стр. 496—504, doi:10.1109/SFCS.1985.9 .

[1]

[2]

[3]

[4]

[5]

[6]