Sortiranje kao funkcija: segmenti i složeni zapisi

MAPA ČASA

Od ideje do prvog C programa

Na kraju je dovoljno da:

• Objasni i ručno prati selection, insertion i bubble sort.
• Nacrtaj bubble sort dijagram toka i odgovori na pitanja 98 i 102.
• Napiši funkciju za sortiranje koja prima smer ili kriterijum.
• Sortiraj svaki segment niza, uključujući poslednji kraći segment.
• Kod struktura menjaj ceo zapis i pravilno obradi dinamički niz.

01 · KORAK

Selection sort postavlja pravi element na sledeće mesto

U svakom prolazu posmatramo još neuređeni deo niza. Za rastući poredak tražimo indeks njegovog najmanjeg elementa, pa taj element menjamo sa a[i]. Posle prolaza i, mesta od 0 do i su završena.

Pamtimo indeks, a ne samo najmanju vrednost, jer su za zamenu potrebna dva mesta u nizu. Spoljašnja petlja staje kod n - 1: kada su svi prethodni elementi postavljeni, poslednji je već na pravom mestu.

for (int i = 0; i < n - 1; i++) {
    int imin = i;
    for (int j = i + 1; j < n; j++)
        if (a[j] < a[imin]) imin = j;
    if (imin != i) zameni(&a[i], &a[imin]);
}

02 · KORAK

Insertion sort ubacuje element u već uređeni levi deo

Pre početka prolaza i, deo a[0] do a[i-1] već je uređen. Vrednost a[i] čuvamo u x, veće prethodnike pomeramo udesno i x upisujemo u otvoreno mesto.

Uslov j >= 0 mora biti prvi u izrazu j >= 0 && a[j] > x. Zahvaljujući kratkom spoju, a[j] se ne čita kada j postane -1.

for (int i = 1; i < n; i++) {
    int x = a[i];
    int j = i - 1;
    while (j >= 0 && a[j] > x) {
        a[j + 1] = a[j];
        j--;
    }
    a[j + 1] = x;
}

03 · KORAK

Bubble sort, zastavica i dijagram toka

Bubble sort poredi susede. Za neopadajući redosled menja ih kada je a[j] > a[j+1]. Posle prvog prolaza najveći element stiže na kraj, pa unutrašnja granica u sledećem prolazu može da bude kraća za i mesta.

Promenljiva zamena počinje nulom na početku svakog spoljašnjeg prolaza. Ako ostane nula, nijedan sused nije bio u pogrešnom redosledu i niz je već uređen.

for (int i = 0; i < n - 1; i++) {
    int zamena = 0;
    for (int j = 0; j < n - 1 - i; j++)
        if (a[j] > a[j + 1]) {
            zameni(&a[j], &a[j + 1]);
            zamena = 1;
        }
    if (zamena == 0) break;
}

04 · KORAK

Smer i kriterijum pripadaju parametrima funkcije

Umesto dve skoro iste funkcije, sortiraj može da primi smer. Na primer, smer 0 bira rastući, a smer 1 opadajući poredak. Telo algoritma ostaje isto; menja se samo odluka da li je trenutni par u pogrešnom redosledu.

Kod složenijih zapisa isti obrazac prima tip kriterijuma. Pomoćna funkcija pogresan_redosled poredi odgovarajuće polje, dok sortiraj vodi petlje i poziva zamenu.

int pogresno = smer == 0
    ? a[j] < a[izabrani]
    : a[j] > a[izabrani];
if (pogresno) izabrani = j;

05 · KORAK

Svaki segment dobija svoj početak i stvarnu dužinu

Ako se niz deli na uzastopne segmente dužine m, početci su 0, m, 2m i tako dalje dok su manji od n. Izraz a + pocetak prosleđuje adresu prvog elementa trenutnog segmenta.

Poslednji segment može biti kraći. Njegova stvarna dužina je min(m, n - pocetak). Prosleđivanje pune vrednosti m dozvolilo bi funkciji da čita izvan niza.

for (int pocetak = 0; pocetak < n; pocetak += m) {
    int k = n - pocetak;
    if (k > m) k = m;
    sortiraj(a + pocetak, k);
}

06 · KORAK

Kod struktura se menja ceo zapis

Ako zapis sadrži naziv, bodove i golove, ta polja pripadaju istoj reprezentaciji. Zamena samo broja bodova odvaja rezultat od naziva. Zato zameni prima pokazivače na dva zapisa i menja dve cele strukture.

Tipičan ispitni zadatak traži dinamički niz struktura, funkciju za zamenu, sortiranje po kriterijumu i rezultat izveden iz uređenog niza. Redosled rada je: validacija n, malloc, provera NULL, unos, pozivi funkcija, ispis i free.

void zameni(Reprezentacija *x, Reprezentacija *y) {
    Reprezentacija p = *x;
    *x = *y;
    *y = p;
}

int pogresan(Reprezentacija x, Reprezentacija y, char tip) {
    return tip == 'b' ? x.bodovi < y.bodovi
                      : x.golovi < y.golovi;
}

ZATVARANJE

Brza provera pre domaćeg

1. Koja je razlika između algoritma i programa?
2. Šta je ime, a šta vrednost promenljive?
3. Kako svojim rečima čitaš x = x + 1?
4. Koji red prvog programa računa, a koji prikazuje rezultat?