Sortovi: Selection, Bubble i Counting

Jedan od najkorisnijih i najkorišćenijih algoritama u programiranju jeste algoritmi za sortiranje (raspoređivanje). Ima ih na stotine, mozda čak i hiljade, ali jedno 15 do 20 "imaju smisla" i koriste se redovno. Ovde ću obraditi tri sorta koja su po meni najjednostavnija (ali ne i najproduktivnija).

Prvo da kažem nešto o zamenjivanju (swap). Ako napišemo a=b; b=a; nećemo zamenjiti vrednosti, hajde da analiziramo. a ima vrednost x, a b ima vrednost y. Kada kažemo a=b, a uzima vrednost b odnosno y, pa je sad vrednost broja a y. Kada kažemo b=a onda b ima vrednost a, odnosno y, dakle b ima vrednost y i a ima vrednost y. Hajde da vidimo kako bih smo to uradili na pravilan način:

int t;

t=a;

a=b;

b=t;

t na početku nema vrednost, kada kažemo t=a, t uzima vrednost broja a, odnosno x, pa t ima vrednost x. Stavljamo da je vrednost broja a=b, odnosno a dobija vrednost y. Na kraju kažemo da broj b dobija vrednost broja t, odnosno x što je početna vrednost broja a. Pogledajte ilustraciju.

Kada smo rešili problem sa zamenjivanjem, hajde da krenemo na sortove.

Selection Sort

Selection Sort je najjednostavniji način za sortiranje, i bazira se na tome da se upoređuje svaki par brojeva u nizu i proverava dali je prvi veći od drugog i, ako jeste, zamenjuje se. To se radi tako što se za prvi član niza prođe kroz sve ostale i proverava ako je trenutni koj gledamo veći, ako jeste zamenimo ih.

for(int i=0; i<n-1; i++)

{

for(int j=i+1; j<n; j++)

{

if(a[i]>a[j])

{

int t;

t=a[i];

a[i]=a[j];

a[j]=t;

}

}

}

Da vam objasnim na primeru: 2 5 1 4 3.

Prvo gledamo prvi član, odnosno 2, i prolazimo kroz sve ostale:

2<5 ništa

2<1 niz: 1 5 2 4 3 (Pošto smo zamenili 2 i 1, sada gledamo 1)

1<4 ništa

1<3 ništa

sada prelazimo na 5.

5>2 niz: 1 2 5 4 3

2<4 ništa

2<3 ništa

prelazimo na 5 (opet)

5>4 niz: 1 2 4 5 3

4>3 niz: 1 2 3 5 4

prelazimo na 5 (o5)

5>4 niz: 1 2 3 4 5

Eto, niz je sad sortiran. Naravno možete da se pitate "Zašto ga uopšte sortiramo?!". Pa dobro pitanje. Recimo onaj primer excela, znate funkciju sort, pa eto. Kada googlate "Science Madness", google sortira ono što treba da izbaci po broju ljudi koji su otišli na taj link, a zatim na prvoj strani ispiše 10-15 linkova koji su najbolji. Evo jedne animacije da vam pomogne.

Bubble Sort

Bubble Sort je relativno sličan selection sortu. On radi tako što se prolazi više puta kroz niz i proveravaju se susedni članovi. Kada naiđemo na neki član tako da a[i]>a[i+1] zamenjujemo ih. Znajući to na kraju će uvek ostati najveći član.

for(int i=n; i>1; i--)

{

for(int j=0; j<i-1; j++)

{

if(a[j]>a[j+1])

{

int t;

t=a[j];

a[j]=a[j+1];

a[j+1]=t;

}

}

}

Sledeća animacija će vam mnogo objasniti.

Counting Sort

Counting Sort radi na potpuno drugačiji način od prethodna dva. Kao što sama reč kaže (counting - eng. brojati) ovaj sort radi tako što izbroji koliko ima članova koje vrste i onda ispisuje sve članove koji postoje. To se radi tako što se napravi novi niz i kad god učitate cifru povećavate član tog niza koji ima indeks učitanog broja.

for(int i=0; i<10000; i++)b[i]=0;
cin>>n;

for(int i=0; i<n; i++)
{
cin>>a[i];
b[a[i]]++;
}
for(int i=0; i<10000; i++)
{
while(b[i]>0)
{
a[m]=i;
m++;
b[i]--;
}
}

Uzmimo primer: 4 7 3 4 2 3
Kada učitavamo brojeve prvo učitavamo 4 i onda b[4] se poveća, zatim se b[7] poveća, pa b[3], na kraju niz b izgleda: 0 0 1 2 2 0 0 1 0 0 0... i onda se svaki indeks ubacuje u niz a b[i] puta.