|
[quote="Anonymous"]Može li mi netko objasniti sortiranje liste pomoću hrpe na primjeru: L=(8,3,5,9,8,2,1,10,3,7,4,10) ?
Hvala unaprijed![/quote]
U početku imamo praznu hrpu.
Zatim idemo kroz listu i brojeve redom ubacujemo u hrpu.
Zatim jedan po jedan vadimo elemente s vrha hrpe i ispisujemo ih van.
Hrpa se reprezentira poljem na standardni način, ako ne znaš kako, viči.
Ovako hrpa raste prilikom ubacivanja svakog pojedinog elementa:[code:1]
(ubacimo 8)
8 (ubacimo 3 na kraj, i on se zamijeni s 8 )
3 8 (ubacimo 5 na kraj, on ostane tamo jer je veći od svog roditelja 3 )
3 8 5 ( 9 ubačen, ostaje na kraju jer mu je roditelj 8 )
3 8 5 9 ( 8 također ostaje, roditelj mu je jednak njemu, druga osmica)
3 8 5 9 8 (ubacujemo 2 koji se zamijeni prvo s 5 , onda s 3 i dođe na vrh)
2 8 3 9 8 5 ( 1 , ista priča - njegov put do vrha je preko 3 i 2 )
1 8 2 9 8 5 3 ( 10 je najveći, pa ostaje na kraju)
1 8 2 9 8 5 3 10 ( 3 se od kraja (9.pozicija) penje 9.->4.->2. )
1 3 2 8 8 5 3 10 9 ( novi 7 se zamijeni sa svojim roditeljem 8 @5. )
1 3 2 8 7 5 3 10 9 8 ( 4 se zamijeni sa 7 , 3 ga zaustavi da ne ide dalje)
1 3 2 8 4 5 3 10 9 8 7 ( zadnja desetka je najveća, pa ostaje na kraju)
1 3 2 8 4 5 3 10 9 8 7 10 (ovo je hrpa nakon svih ubacivanja)[/code:1]
Sad krećemo s izbacivanjima... kako izbacujemo elemente, pišemo ih na output:[code:1]
1 3 2 8 4 5 3 10 9 8 7 10 (izbacimo 1 , izbrišemo 10 s kraja i stavimo ga na njegovo - prvo - mjesto. Nakon toga 10 se zamijeni s manjim od svoje djece - 3 i 2 , dakle 2 , pa onda dalje - manji od 5 i 3 je 3 na 6. mjestu, dalje ne treba jer 12. mjesta više nema)
2 3 3 8 4 5 10 10 9 8 7 (izbacimo 2 , 7 ide: 1.->3.(svejedno)->6. )
3 3 5 8 4 7 10 10 9 8 (izbacimo 3 , 8: 1.->2.->5.)
3 4 5 8 8 7 10 10 9 (izbacimo još jednu 3 , 9: 1.->2.->5.(svejedno))
4 8 5 8 9 7 10 10 (izbacimo 4 , 10 se zamijeni s 5 i kasnije 7 )
5 8 7 8 9 10 10 (izbacimo 5 , opet 10 s kraja ode na 1. , pa na 3.)
7 8 10 8 9 10 (izbacimo 7 , 10 s kraja na početak, i gurne osmice gore)
8 8 10 10 9 (izbacimo (i ispišemo) prvu osmicu, 9 završi na 2. mjestu)
8 9 10 10 (i druga osmica van, na output, 10 se s početka zamijeni s 9 )
9 10 10 (postaje trivijalno: devetka van, 10 na njeno mjesto)
10 10 (prva desetka van, druga na njeno mjesto)
10 (i ta desetka van - pogledajmo output: 1,2,3,3,4,5,7,8,8,9,10,10 . Jupi.)
[/code:1]
A sad nađi neki monitor s dovoljno velikom rezolucijom... :-o :- ))
| Anonymous (napisa): | Može li mi netko objasniti sortiranje liste pomoću hrpe na primjeru: L=(8,3,5,9,8,2,1,10,3,7,4,10) ?
Hvala unaprijed! |
U početku imamo praznu hrpu.
Zatim idemo kroz listu i brojeve redom ubacujemo u hrpu.
Zatim jedan po jedan vadimo elemente s vrha hrpe i ispisujemo ih van.
Hrpa se reprezentira poljem na standardni način, ako ne znaš kako, viči.
Ovako hrpa raste prilikom ubacivanja svakog pojedinog elementa: | Kod: |
(ubacimo 8)
8 (ubacimo 3 na kraj, i on se zamijeni s 8 )
3 8 (ubacimo 5 na kraj, on ostane tamo jer je veći od svog roditelja 3 )
3 8 5 ( 9 ubačen, ostaje na kraju jer mu je roditelj 8 )
3 8 5 9 ( 8 također ostaje, roditelj mu je jednak njemu, druga osmica)
3 8 5 9 8 (ubacujemo 2 koji se zamijeni prvo s 5 , onda s 3 i dođe na vrh)
2 8 3 9 8 5 ( 1 , ista priča - njegov put do vrha je preko 3 i 2 )
1 8 2 9 8 5 3 ( 10 je najveći, pa ostaje na kraju)
1 8 2 9 8 5 3 10 ( 3 se od kraja (9.pozicija) penje 9.->4.->2. )
1 3 2 8 8 5 3 10 9 ( novi 7 se zamijeni sa svojim roditeljem 8 @5. )
1 3 2 8 7 5 3 10 9 8 ( 4 se zamijeni sa 7 , 3 ga zaustavi da ne ide dalje)
1 3 2 8 4 5 3 10 9 8 7 ( zadnja desetka je najveća, pa ostaje na kraju)
1 3 2 8 4 5 3 10 9 8 7 10 (ovo je hrpa nakon svih ubacivanja) |
Sad krećemo s izbacivanjima... kako izbacujemo elemente, pišemo ih na output: | Kod: |
1 3 2 8 4 5 3 10 9 8 7 10 (izbacimo 1 , izbrišemo 10 s kraja i stavimo ga na njegovo - prvo - mjesto. Nakon toga 10 se zamijeni s manjim od svoje djece - 3 i 2 , dakle 2 , pa onda dalje - manji od 5 i 3 je 3 na 6. mjestu, dalje ne treba jer 12. mjesta više nema)
2 3 3 8 4 5 10 10 9 8 7 (izbacimo 2 , 7 ide: 1.->3.(svejedno)->6. )
3 3 5 8 4 7 10 10 9 8 (izbacimo 3 , 8: 1.->2.->5.)
3 4 5 8 8 7 10 10 9 (izbacimo još jednu 3 , 9: 1.->2.->5.(svejedno))
4 8 5 8 9 7 10 10 (izbacimo 4 , 10 se zamijeni s 5 i kasnije 7 )
5 8 7 8 9 10 10 (izbacimo 5 , opet 10 s kraja ode na 1. , pa na 3.)
7 8 10 8 9 10 (izbacimo 7 , 10 s kraja na početak, i gurne osmice gore)
8 8 10 10 9 (izbacimo (i ispišemo) prvu osmicu, 9 završi na 2. mjestu)
8 9 10 10 (i druga osmica van, na output, 10 se s početka zamijeni s 9 )
9 10 10 (postaje trivijalno: devetka van, 10 na njeno mjesto)
10 10 (prva desetka van, druga na njeno mjesto)
10 (i ta desetka van - pogledajmo output: 1,2,3,3,4,5,7,8,8,9,10,10 . Jupi.)
|
A sad nađi neki monitor s dovoljno velikom rezolucijom...  :- ))
|
