Sortiranje prebrojavanjem

U informatici, sortiranje prebrojavanjem (counting sort) predstavlja algoritam za sortiranje pomoću celih brojeva, tj. algoritam celobrojnog sortiranja. Algoritam radi tako što prebrojava koliko se puta svaki element niza javlja i na osnovu toga određuje poziciju svakog elementa u izlaznom nizu. Vremenska složenost algoritma je linearna i zavisi od broja vrednosti koje se sortiraju i razlike najveće i najmanje vrednosti. Zbog toga je ovaj algoritam pogodan za sortiranje nizova kod kojih razlika između najveće i najmanje vrednosti nije značajno veća od ukupnog broja elemenata. Sortiranje prebrojavanjem se koristi kao deo radiks sortiranja koji mnogo efikasnije sortira velike vrednosti.^[1]^[2]^[3]

Pošto algoritam koristi vrednosti elemenata niza kao indekse za pomoćni niz, ne podleže ograničenju koje imaju algoritmi poređenja, da je složenost u najgorem slučaju O(n logn) . Radiks sortiranja se može iskoristiti za slične probleme kao i sortiranje prebrojavanjem; međutim za segmentno sortiranje su potrebne povezane liste, dinamički nizovi ili velika količina unapred alocirane memorije za čuvanje elemenata u svakom segmentu. Za razliku od segmentnog sortiranja, sortiranje prebrojavanjem koristi jedan broj za svaki segment.

Ulaz i Izlaz uredi

U većini slučajeva, ulaz u algoritam je n elemenata, gde svaki element predstavlja nenegativan ceo broj čija vrednost nije veća od k.^[3] U nekim definicijama ulaz se navodi kao niz celih brojeva,^[1] ali ovo pojednostavljenje ne odgovara mnogim primenama ovog algoritma. Na primer kada se koristi kao deo radiks sortiranja ulaz predstavljaju pojedinačne cifre brojeva koji se sortiraju.

U većini slučajeva kada se ovaj algoritam primenjuje, npr. radiks sortiranje, maksimalna vrednost elementa mvar|k je unapred poznata, i kao takva predstavlja deo ulaznih vrednosti. U slučaju da mvar|k nije poznato, može se preračunati uvođenjem dodatne petlje koja određuje maksimalnu vrednost elemenata.

Izlaz je sortirani niz elemenata. Zbog primene kod radiks sortiranja veoma je važno da sortiranje prebrojavanjem bude stabilan; u slučaju kada dva elementa imaju isti ključ, trebalo bi da imaju isti poredak u izlaznom kao i u ulaznom nizu.^[1]^[2]

Algoritam uredi

Neka je dato n elemenata, koji predstavljaju cele brojeve iz opsega od 1 do m, m≥n. Rezerviše se m lokacija, a onda se za svako i broj xi stavlja na lokaciju xi koja odgovara njegovoj vrednosti. Posle toga se redom pregledaju sve lokacije i iz njih se pokupe elementi. Složenost ovog algoritma je O(m + n).^[4]

Implementacija u C kodu:

#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]);
}

Modifikovana verzija uredi

Određuje se najmanja i najveća vrednost ulaznog niza a. Broj pojavljivanja članova niza a pamti se u pomoćnom nizu o prolaskom kroz elemente niza u intervalu od najmanjeg do najvećeg.^[4]

Implementacija u C++ kodu:

#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]);

}

Varijacije algoritma uredi

Za podatke u kojima je maksimalna veličina ključa znatno manja od broja elemenata, algoritam može biti paralelizovan razdvajanjem ulaza u približno jednake podnizove, paralelnim obrađivanjem svakog podniza i generisanjem odvojenog niza pojavljivanja elemenata za svaki podniz, i konačno spajanjem nizova pojavljivanja. Kada se koristi kao deo paralelnog algoritma radiks sortiranja, veličina ključa bi trebalo da odgovara veličini podeljenih podnizova.^[5] Jednostavnost algoritma prebrojavanjem i laka paralelizacija ga čine upotrebljivim u paralelnim algoritmima finije strukture.^[6]

Kao što je opisano, algoritam sortiranja prebojavanjem nije algoritam za sortiranje u mestu; čak iako se zanemari niz pojavljivanja, potrebni su mu odvojeni ulazni i izlazni nizovi. Modifikacija u kojoj se elementi čuvaju sortirani u istom nizi koji je dat na ulazu je moguća, prikazana ranije; međutim pri takvoj modifikaciji algoritam gubi stabilnost.^[3]

Reference uredi

^ ^a ^b ^v Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), „8.2 Counting Sort”, Introduction to Algorithms (2nd izd.), MIT Press and McGraw-Hill, str. 168—170, ISBN 0-262-03293-7 . See also the historical notes on page 181.
^ ^a ^b Edmonds, Jeff (2008), „5.2 Counting Sort (a Stable Sort)”, How to Think about Algorithms, Cambridge University Press, str. 72—75, ISBN 978-0-521-84931-9 .
^ ^a ^b ^v Sedgewick, Robert (2003), „6.10 Key-Indexed Counting”, Algorithms in Java, Parts 1-4: Fundamentals, Data Structures, Sorting, and Searching (3rd izd.), Addison-Wesley, str. 312—314 .
^ ^a ^b Preuzeto iz predavanja "Konstrukcija i analiza algoritama 2", Jelene Hadži-Purić. Matematički fakultet, Univerzitet u Beogradu
^ 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, str. 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), str. 496—504, doi:10.1109/SFCS.1985.9 .

Spoljašnje veze uredi

Counting Sort html5 visualization
Demonstration applet from Cardiff University Arhivirano na sajtu Wayback Machine (2. jun 2013)
Efficient Counting Sort in Haskell Arhivirano na sajtu 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] v Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), „8.2 Counting Sort”, Introduction to Algorithms (2nd izd.), MIT Press and McGraw-Hill, str. 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, str. 72—75, ISBN 978-0-521-84931-9 .

[sedgewick-3] v Sedgewick, Robert (2003), „6.10 Key-Indexed Counting”, Algorithms in Java, Parts 1-4: Fundamentals, Data Structures, Sorting, and Searching (3rd izd.), Addison-Wesley, str. 312—314 .

[autogenerated1-4] Preuzeto iz predavanja "Konstrukcija i analiza algoritama 2", Jelene Hadži-Purić. Matematički fakultet, Univerzitet u Beogradu

[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, str. 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), str. 496—504, doi:10.1109/SFCS.1985.9 .

[1]

[2]

[3]

[4]

[5]

[6]