=== 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:\\ 
\\ 
|B|X|X|1|X|X|X|X|		
|B|X|X|1|2|X|X|X|		
|B|X|X|1|2|X|4|X|
|B|X|1|1|2|X|4|X|
|B|X|1|1|2|X|4|5|
|B|X|1|1|2|4|4|5|
|**B**|**1**|**1**|**1**|**2**|**4**|**4**|**5**|

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**.\\ 
\\ 
<code pascal>
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.</code>
\\ 

<code c> 
/* 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]);
}</code>
\\ 

<code pascal> 
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.</code>
\\ 

<code c> 
/* 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]);
}</code>
\\ 


----


[[programiranje-sortiranje|Back]] Contact:<bblef@live.com>