Osnovni algoritmi za rad sa nizovima - treći deo

Od često korišćenih postupaka u radu sa nizovima treba još da upoznamo SORTIRANJE tj. promenu redosleda elemenata tako da budu složeni prema nekom kriterijumu - najšešće rastuće ili opadajuće.

Postoji veći broj algoritama kojima se ovo postiže a razlikuju se po brzini izvršavanja. Jednostavniji za pisanje su uglavnom nedovoljno brzi ako niz ima veliki broj elemenata. Pokazaćemo nekoliko najpoznatijih algoritama. Klikom na link odgledajte demonstraciju algoritma a potom pogledajte program koji radi po tom algoritmu - sortira se niz a koji ima na elemenata u rastući poredak. QUICK sort je najbrži od navedenih i sortira niz a od pozicije beg do pozicije end. Biće vam jasniji kada objasnimo rekurziju (u sledećem članku).

SELECTION sort

for(i=0; i<na-1; i++)
{
    jmin = i;
    for(j=i+1; j<na; j++)
    {
        if(a[j]<a[jmin])
        jmin=j;
    }
    t = a[jmin];
    a[jmin]= a[i];
    a[i] = t;
}

BUBBLE sort

do
{
    promena = 0;
    for (i = 0; i < na - 1; i++)
    {
        if (a[i] > a[i + 1])
        {
            promena = 1;
            t = a[i];
            a[i] = a[i+1];
            a[i+1] = t;
        }
    }
}
while (promena);

QUICK sort

void quickSort(int a[], int beg, int end)
{
    int i, t, wall;
    if (end == beg)
        return;
    wall = beg;
    for (i = beg; i < end; i++)
    {
        if (a[i] < a[end])
        {
            t = a[wall];
            a[wall] = a[i];
            a[i] = t;
            wall++;
        }
    }
    t = a[wall];
    a[wall] = a[end];
    a[end] = t;
    if (wall > beg)
        quickSort(a, beg, wall - 1);
    if (wall < end)
        quickSort(a, wall + 1, end);
}