MAPA ČASA
Pretraži → pronađi indeks → pomeri → promeni n → uredi niz
1
pretraga
2
prvi i poslednji indeks
3
brisanje
4
ubacivanje
5
bubble sort
Na kraju je dovoljno da:
- Pronađi prvo i poslednje pojavljivanje tražene vrednosti i prebroj sva pojavljivanja.
- Obriši element pomeranjem ostatka niza ulevo.
- Ubaci element na zadati indeks pomeranjem elemenata udesno.
- Prati jedan prolaz bubble sort-a i napiši ceo algoritam za neopadajući redosled.
- Nacrtaj strukturni dijagram toka bubble sort algoritma.
01 · KORAK
Pretraga obilazi elemente redom
Linearna pretraga poredi traženu vrednost x sa a[0], a[1] i tako dalje. Ako nam treba samo prvo pojavljivanje, petlju možemo prekinuti čim pronađemo prvi pogodak.
Promenljiva prvi počinje od -1 zato što -1 nije važeći indeks. Ako posle petlje i dalje ima vrednost -1, element ne postoji u važećem delu niza.
int prvi = -1;
for (int i = 0; i < n; i++) {
if (a[i] == x) {
prvi = i;
break;
}
}
Prvo pojavljivanjeZa niz 4, 7, 4, 9, 4, 2 i x = 4 prati indekse dok se ne pronađe prvi pogodak. Ponovi za x = 6.
Vrednost i indeks nisu istox je vrednost koju tražimo, a prvi je njena pozicija. Ako je prvi = 2, tražena vrednost se nalazi u a[2].
02 · KORAK
Jedan prolaz može da pronađe prvo, poslednje i koliko
Ako su nam potrebna sva pojavljivanja, petlja ne sme da se prekine na prvom pogotku. Brojač se povećava svaki put kada je a[i] jednako x.
Prvi indeks upisujemo samo pri prvom pogotku, a poslednji ažuriramo pri svakom. Tako posle jedne petlje imamo sva tri podatka.
int prvi = -1, poslednji = -1, koliko = 0;
for (int i = 0; i < n; i++) {
if (a[i] == x) {
if (prvi == -1) prvi = i;
poslednji = i;
koliko++;
}
}
Prati tri rezultataZa niz 5, 1, 5, 5, 8 i x = 5 odredi prvi, poslednji i koliko. Zatim predvidi rezultat za x = 7.
Kada x ne postojiprvi i poslednji ostaju -1, a koliko ostaje 0. To su tri saglasna podatka, ne tri posebna slučaja.
03 · KORAK
Brisanje zatvara prazno mesto pomeranjem ulevo
Ako brišemo a[k], element a[k + 1] prelazi na njegovo mesto, zatim a[k + 2] na sledeće i tako do kraja važećeg dela niza.
Posle pomeranja smanjujemo n. Kapacitet niza ostaje isti; samo je jedan element manje važeći.
for (int i = k; i < n - 1; i++) {
a[i] = a[i + 1];
}
n--;
Obriši element na indeksu 1Počni nizom 8, 3, 5, 1, 9. Posle svake dodele napiši trenutno stanje, a zatim označi koji deo niza važi posle n--.
Granica štiti poslednji indeksNajveće i u petlji je n - 2, pa je najveći pročitani indeks i + 1 jednak n - 1. Zbog toga nema pristupa a[n].
04 · KORAK
Ubacivanje prvo pravi slobodno mesto
Da bismo ubacili x na indeks k, postojeće elemente od k do n - 1 pomeramo jedno mesto udesno. Tek zatim upisujemo x u a[k] i povećavamo n.
Pomeranje mora da ide od kraja. Kada bismo krenuli od k, prepisali bismo vrednost koja tek treba da bude kopirana. Pre ubacivanja mora da postoji slobodno mesto u nizu.
for (int i = n; i > k; i--) {
a[i] = a[i - 1];
}
a[k] = x;
n++;
Ubaci 7 na indeks 2Za važeći niz 3, 6, 8, 11 prati kopiranja od kraja ka početku, zatim upiši 7 i odredi novu vrednost n.
Dozvoljene pozicijeZa niz sa n elemenata ubacivanje je moguće na indeksima od 0 do n. k = 0 znači početak, a k = n dodavanje na kraj.
05 · KORAK
Bubble sort poredi susedne elemente
U jednom prolazu porede se a[j] i a[j + 1]. Ako je levi veći, njihove vrednosti se zamene. Zatim se prelazi na sledeći susedni par.
Posle prvog celog prolaza najveći element obrađenog dela sigurno je na kraju. Ostatak niza još ne mora da bude uređen.
for (int j = 0; j < n - 1; j++) {
if (a[j] > a[j + 1]) {
int pomocna = a[j];
a[j] = a[j + 1];
a[j + 1] = pomocna;
}
}
Prvi prolaz kroz 7, 3, 5, 2, 8Posle svakog poređenja napiši ceo niz. Na kraju označi element čija je konačna pozicija sigurna.
Ne preskači stanje posle zameneSledeći par koristi niz kakav je ostao posle prethodnog poređenja, a ne početni niz.
06 · KORAK
Više prolaza uređuje ceo niz
Spoljašnja petlja određuje broj prolaza. Posle svakog prolaza još jedan najveći element nalazi se na svom mestu, pa unutrašnja petlja može da stane ranije.
Za neopadajući redosled zamenjujemo susede kada je a[j] > a[j + 1]. Za nerastući redosled uslov se obrće.
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) {
int pomocna = a[j];
a[j] = a[j + 1];
a[j + 1] = pomocna;
}
}
}
Vežbaonica · Čas 08Zadaci 1–3 vežbaju pretragu, 4–6 brisanje i ubacivanje, a 7 i 8 jedan prolaz i ceo bubble sort. Program prvo sastavi na papiru, pa ga proveri na sajtu.
Pitanje sa ispitaNacrtati strukturni dijagram toka algoritma koji niz A sa N elemenata uređuje u neopadajući redosled. Nabrojati nazive tri algoritma za sortiranje nizova. Nazivi iz gradiva su selection sort, insertion sort i bubble sort.
ZATVARANJE
Provera Časa 08
- Zašto se indeks pre pretrage često postavlja na -1?
- Kako se razlikuju prvo pojavljivanje, poslednje pojavljivanje i broj pojavljivanja?
- Koje su granice petlje koja briše element na indeksu k?
- Zašto se pri ubacivanju niz pomera od kraja ka indeksu k?
- Šta je sigurno tačno posle jednog celog prolaza bubble sort-a?
- Koje granice imaju spoljašnja i unutrašnja petlja bubble sort-a?
