Izpitno vprašanje RAČ2PRA 13000

Iz MaFiRaWiki

GFDL Avtor tega članka je študent/ka Marjetaselak.

Pripravil/a ga je pri predmetu Računalništvo 2 (FMF PRA).


Kljub temu ste vsi vabljeni k urejanju in popravkom, saj je bistvo wikija ravno v sodelovalnem delu.

Vsebina

Vprašanje

Na praktičnem primeru pokaži, kako deluje hitro urejanje in urejanje z zlivanjem.

Odgovor

Hitro urejanje

Izberemo si delilni element. Poimenujemo ga pivot. Ponavadi je to prvi element v tabeli. Gledamo iz leve, in ko najdemo element, ki je večji od pivota, si ga zapomnimo. Potem gledamo še z desne, tukaj pa iščemo element, ki je manjši od pivota, ko naletimo na tak element si ga zopet zapomnimo. Potem ta dva elementa zamenjamo. To delamo toliko časa, dokler indeksa nista prekrižana. Ko prideta indeksa skupaj, se prekrižata postavimo mejo. Tako imamo tabelo razdeljeno na dva dela. Na levi strani so elementi manjši ali enaki pivotu, na desni strani pa elementi večji ali enaki pivotu. Z istim postopkom uredimo oba dela.

primer

slika:hitroUrejanje.png

slika:hitroUrejanje2.png

Urejanje z zlivanjem

Tabelo razdelimo na posamezne elemente (razdelimo jo na polovico, te polovice še na pol itn.). Ko združujemo / zlivamo, pomeni da elemente urejamo.

primer

slika:urejanjeZzlivanjem1.png

slika:urejanjeZzlivanjem2.png

slika:urejanjeZzlivanjem3.png

slika:urejanjeZzlivanjem4.png

Osebna orodja