This is an old revision of the document!


Counting sort(sortiranje prebrojavanjem)

Ovaj, takođe stabilan, algoritam se koristi za sortiranje lista kod kojih je ključ po kome
se sortira prirodan, odnosno ceo broj (mada se ideja može iskoristiti za sve vrste lista
kod kojih je ključ iz nekog konačnog opsega). Za njegov rad je potrebno određivanje
maksimalne vrednosti ključa (ako su prirodni brojevi pitanju). Ideja je da se za formiranje
izlazne liste koristi pomoćna lista, čiji su indeksi vrednosti u intervalu od 0 do
maksimalne vrednosti ključa. Ta lista ima zadatak da prebroji pojavljivanja svih brojeva
iz skupa „mogućih” vrednosti, i dobija se jednim prolazom kroz ulaznu listu. Na osnovu
pomoćne liste algoritam rekonstruiše sortiranu izlaznu listu.
Kompleksnost ovog algoritma je O(n+k) , gde je k maksimalna vrednost
ključa. Očigledno, k bi trebao da bude osetno manji u odnosu na n, da ne bi imao bitnog
uticaja na brzinu rada.
Primer algoritama (program counting_sort1;) koji sortira niz prirodnih brojeva, pri čemu
brojevi imaju vrednosti do k, a ima ih n. Niz a je niz koji se zadaje na ulazu, onaj niz koji
treba sortirati. U nizu b se pamti sortiran niz a, a c[i] je broj pojavljivanja broja i u nizu a u
drugoj petlji, a u trećoj petlji c[i] je poslednje mesto u nizu gde se pojavljuje broj i.
Druga for petlja inicijalizuje niz c tako da vrednost svih njegovih članova
bude 0. Treća for petlja formira niz c, odnosno broji koliko puta se svaki član niza a[i]
pojavljuje i tu vrednost pamti na a[i]-tom mestu u nizu c. Četvrta for petlja sabira u i-ti
član niza c sve one članove pre njega, čime se postiže da c[i] sada pokazuje na kojem će se
mestu poslednji put pojaviti i. Peta for petlja formira niz b, tako što se, najpre, na c[i]-to
mesto u niz b postavi taj broj a[i], pa pošto je ono sada popunjeno, c[i] se smanjuje za
jedan. Postupak se ponavlja dok se ne formira ceo niz b.
Primer:Ako se unese niz a: 1,4,5,1,4,2,1, b i c će se kroz program menjati na sledeći
način:
Posle treće petlje:

A 1 4 5 1 4 2 1 || C 3 1 0 2 1

Posle četvrte petlje:

C 3 4 4 6 7

Posle pete petlje:

BXX1XXXX
BXX12XXX
BXX12X4X
BX112X4X
BX112X45
BX112445
B1112445

Poboljšana verzija (program counting_sort2;) određuje min i max niza, prebrojava
pojavljivanje članova niza a, što se pamti na nizu o, prolaskom i, čiji broj
pojavljivanja o[i], od min do max formira se sortiran niz a.

program counting_sort1;
var a,b,c:array [1..100] of integer;
i,j,k,n:integer;
begin read(n,k);
for i:=1 to n do read(a[i]);
for i:=1 to k do c[i]:=0;
for j:=1 to n do c[a[j]]:=c[a[j]]+1;
for i:=2 to k do c[i]:=c[i]+c[i-1];
for j:=n downto 1 do
begin
 b[c[a[j]]]:=a[j]; c[a[j]]:=c[a[j]]-1;
end;
for i:=1 to n do write(b[i]:4);
end.


/* program counting_sort1;*/
#include<stdio.h>
main()
{int i,j,k,n;
int a[100],b[100],c[100];
scanf("%d%d",&n,&k);
for (i=1;i<=n;i++) scanf("%d",&a[i]);
for (i=1;i<=k;i++) c[i]=0;
for (j=1;j<=n;j++) c[a[j]]=c[a[j]]+1;
for (i=2;i<=k;i++) c[i]=c[i]+c[i-1];
for (j=n;j>=1;j--)
{ b[c[a[j]]]=a[j]; c[a[j]]=c[a[j]]-1;}
for (i=1;i<=n;i++) printf("%d ",b[i]);
}


program counting_sort2;
var i,j,n,min,max,k:integer;
a:array[1..200] of integer;
o:array[1..900] of integer;
begin 
readln(n);
min:=maxint; max:=0; k:=0;
fillchar(o,sizeof(o),0);
for i:=1 to n do begin
readln(a[i]);
o[a[i]]:=o[a[i]]+1;
if a[i]>max then max:=a[i];
if a[i]<min then min:=a[i];
end;
for i:=min to max do if o[i]<>0 then
for j:=1 to o[i] do
begin
k:=k+1;  a[k]:=i;
end;  {k=n}
for i:=1 to n do write(a[i],' ');
end.


/* program counting_sort2;*/
#include<stdio.h>
main()
{
int i,j,n,min,max,k;
int a[200],o[900];
scanf("%d",&n);
min=32700;max=0;k=0;
for (j=0;j<=900;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]);
}



Back Contact:bblef@live.com

 
programiranje-sortiranje-counting_sort.1323269363.txt.gz · Last modified: 2011/12/07 15:49 by milos.furtula
 
Except where otherwise noted, content on this wiki is licensed under the following license:CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki