|
evo, danas sam nekome tipkao kilogram teksta u vezi qsorta, pa ako ce kome trebat...
(original na hr.org.fer)
> Molio bi nekoga da rijesi ovaj zadatak:
>
> Ilustrirati i opisati osnovne rekurzivne korake uzlaznog Quicksorta za
> podatke : 12 2 21 18 50 41 19 20 7 15 3
>
> Kao stozer izabire se prvi clan !!!
[ !12! 2 21 18 50 41 19 20 7 15 3 ]
sa [] cu oznacit koji dio niza gledas trenutno, sa _ onog koji je stavljen na mjesto, a sa ! stozer.
Uzmes prvi clan kao stozer.
Cilj ti ga je postaviti u niz tako da su svi lijevo od njega manji ili jednaki njemu, a svi desno veci ili jednaki. tada ces moci pozvati sort za lijevu i desnu polovicu, te ce nakon toga niz biti sortiran.
dakle, stozer je 12.
ides slijeva, trazis veci element - dodjes do 21
ides zdesna, trazis manji element - dodjes do 3
zamjenis
[ !12! 2 3 18 50 41 19 20 7 15 21 ]
ides dalje sljeva, dodjes na 18
ides dalje zdesna, dodjes na 7
zamjenis
[ !12! 2 3 7 50 41 19 20 18 15 21 ]
ides dalje sljeva, dodjes do 50
ides dalje zdesna, dodjes na 7.
ali sad su se "prekrizili" pokazivaci slijeva i zdesna, pa umjesto da ih zamjenimo, zamjenimo stozer i pokazivac zdesna (7).
[ 7 2 3 _12_ 50 41 19 20 18 15 21 ]
sad pozovemo sort za lijevu i desnu polovicu
prvo lijevu
[ !7! 2 3 ] 12 50 41 19 20 18 15 21
desni pokazivac pokaze na 3, lijevi ode na kraj niza.
opet su se prekrizili, zamjenimo stozer i 3.
[ 3 2 _7_ ] 12 50 41 19 20 18 15 21
pozovemo za lijevu i desnu polovicu (desne nema :)
[ !3! 2 ] _7_ 12 50 41 19 20 18 15 21
zamjenimo 3 i 2.
[ 2 _3_ ] 7 12 50 41 19 20 18 15 21
sad se rekurzija vraca tamo do kad nam je 12 bio stozer
2 3 7 12 [ !50! 41 19 20 18 15 21 ]
desni pokazivac nadje 12, ali lijevi ode do kraja.
dakle, zamjenimo 50 i 21.
2 3 7 12 [ 21 41 19 20 18 15 _50_ ]
pozovemo za obje polovice, ovaj put opet nema desne.
2 3 7 12 [ !21! 41 19 20 18 15 ] 50
lijevi pokazivac nadje 41, desni nadje 15. to zamjenimo
2 3 7 12 [ !21! 15 19 20 18 41 ] 50
lijevi nadje 41, desni nadje 18. ali prekrizili su se, pa zamjenimo 18 i 21.
2 3 7 12 [ 18 15 19 20 _21_ 41 ] 50
pozovemo lijevu i desnu polovicu
2 3 7 12 [ !18! 15 19 20 ] 21 41 50
slijeva nadjemo 19, zdesna 15. opet su se prekrizli, pa zamjenimo 18 i 15.
2 3 7 12 [ 15 _18_ 19 20 ] 21 41 50
pozovemo za lijevu polovicu (ovdje se moze napraviti uvjet da se ne poziva ako je samo jedan element).
2 3 7 12 [ !15! ] 18 19 20 21 41 50
lijevi predje, desni nadje samog sebe. dakle, zamjeni se sam sa sobom. (ili se uopce ne zamjeni, ovisi o implementaciji)
2 3 7 12 15 [ !18! 19 ] 20 21 41 50
tu se opet 18 zamjeni sam sa sobom.
sad se vraca rekurzija u "negdje davno" :)
2 3 7 12 15 18 19 20 21 [ !41! ] 50
opet se 41 zamjeni sam sa sobom.
rekurzija se vrati skroz na pocetak i to je to.
evo, danas sam nekome tipkao kilogram teksta u vezi qsorta, pa ako ce kome trebat...
(original na hr.org.fer)
> Molio bi nekoga da rijesi ovaj zadatak:
>
> Ilustrirati i opisati osnovne rekurzivne korake uzlaznog Quicksorta za
> podatke : 12 2 21 18 50 41 19 20 7 15 3
>
> Kao stozer izabire se prvi clan !!!
[ !12! 2 21 18 50 41 19 20 7 15 3 ]
sa [] cu oznacit koji dio niza gledas trenutno, sa _ onog koji je stavljen na mjesto, a sa ! stozer.
Uzmes prvi clan kao stozer.
Cilj ti ga je postaviti u niz tako da su svi lijevo od njega manji ili jednaki njemu, a svi desno veci ili jednaki. tada ces moci pozvati sort za lijevu i desnu polovicu, te ce nakon toga niz biti sortiran.
dakle, stozer je 12.
ides slijeva, trazis veci element - dodjes do 21
ides zdesna, trazis manji element - dodjes do 3
zamjenis
[ !12! 2 3 18 50 41 19 20 7 15 21 ]
ides dalje sljeva, dodjes na 18
ides dalje zdesna, dodjes na 7
zamjenis
[ !12! 2 3 7 50 41 19 20 18 15 21 ]
ides dalje sljeva, dodjes do 50
ides dalje zdesna, dodjes na 7.
ali sad su se "prekrizili" pokazivaci slijeva i zdesna, pa umjesto da ih zamjenimo, zamjenimo stozer i pokazivac zdesna (7).
[ 7 2 3 _12_ 50 41 19 20 18 15 21 ]
sad pozovemo sort za lijevu i desnu polovicu
prvo lijevu
[ !7! 2 3 ] 12 50 41 19 20 18 15 21
desni pokazivac pokaze na 3, lijevi ode na kraj niza.
opet su se prekrizili, zamjenimo stozer i 3.
[ 3 2 _7_ ] 12 50 41 19 20 18 15 21
pozovemo za lijevu i desnu polovicu (desne nema :)
[ !3! 2 ] _7_ 12 50 41 19 20 18 15 21
zamjenimo 3 i 2.
[ 2 _3_ ] 7 12 50 41 19 20 18 15 21
sad se rekurzija vraca tamo do kad nam je 12 bio stozer
2 3 7 12 [ !50! 41 19 20 18 15 21 ]
desni pokazivac nadje 12, ali lijevi ode do kraja.
dakle, zamjenimo 50 i 21.
2 3 7 12 [ 21 41 19 20 18 15 _50_ ]
pozovemo za obje polovice, ovaj put opet nema desne.
2 3 7 12 [ !21! 41 19 20 18 15 ] 50
lijevi pokazivac nadje 41, desni nadje 15. to zamjenimo
2 3 7 12 [ !21! 15 19 20 18 41 ] 50
lijevi nadje 41, desni nadje 18. ali prekrizili su se, pa zamjenimo 18 i 21.
2 3 7 12 [ 18 15 19 20 _21_ 41 ] 50
pozovemo lijevu i desnu polovicu
2 3 7 12 [ !18! 15 19 20 ] 21 41 50
slijeva nadjemo 19, zdesna 15. opet su se prekrizli, pa zamjenimo 18 i 15.
2 3 7 12 [ 15 _18_ 19 20 ] 21 41 50
pozovemo za lijevu polovicu (ovdje se moze napraviti uvjet da se ne poziva ako je samo jedan element).
2 3 7 12 [ !15! ] 18 19 20 21 41 50
lijevi predje, desni nadje samog sebe. dakle, zamjeni se sam sa sobom. (ili se uopce ne zamjeni, ovisi o implementaciji)
2 3 7 12 15 [ !18! 19 ] 20 21 41 50
tu se opet 18 zamjeni sam sa sobom.
sad se vraca rekurzija u "negdje davno" :)
2 3 7 12 15 18 19 20 21 [ !41! ] 50
opet se 41 zamjeni sam sa sobom.
rekurzija se vrati skroz na pocetak i to je to.
_________________  |
