| Prethodna tema :: Sljedeća tema |
| Autor/ica |
Poruka |
raspjevani_opat
Forumaš(ica)
Pridružen/a: 04. 02. 2005. (12:42:04)
Postovi: (E5)16
|
|
| [Vrh] |
|
mdoko
Forumaš(ica)
Pridružen/a: 30. 11. 2002. (22:17:12)
Postovi: (71A)16
Spol: 
Lokacija: Heriot-Watt University, Edinburgh
|
|
| [Vrh] |
|
veky
Forumaš(ica)
Pridružen/a: 09. 12. 2002. (19:59:43)
Postovi: (5B0)16
Lokacija: negdje daleko...
|
 Postano: 22:26 ned, 6. 2. 2005 Naslov: Re: merge sort |
    |
|
|
[quote="raspjevani_opat"]jel bi netko bio toliko dobar pa napisao merge sort u pseudo c-u?[/quote]
Pa zar to ne postoji u The skripti? :-o
Ukratko ideja (za polja duljine 2^n ): imaš dva polja, u prvom je u početku početni niz. Sad u drugo pišeš elemente iz prvog, samo ih sad shvatiš kao 2^n lista duljine 1 . I pritom ih mergeaš (vjerujem da osnovni merge znaš napisati, ako ne javi), 2i-tu s (2i+1)-vom. I to pišeš na njima odgovarajuća mjesta u drugom polju. Nakon što napraviš jedan prolaz, prepišeš drugo polje natrag u prvo (puno efikasnije ako imaš pointere na polja da ih samo zamijeniš, no to je već stvar implementacije), i ponavljaš isto s listama duljine 2 . Dakle sad mergeaš (u prethodnom koraku sortirane) (a[0],a[1]) i (a[2],a[3]) u jednu "listu" duljine 4 , i nju pišeš u b[0]..b[3] . Zatim isto s (a[4],a[5]) i (a[6],a[7]) , u b[4]..b[7] , itd. Nakon toga opet povećaš duljine listi u pitanju duplo, zamijeniš polja (ili prepišeš b u a ), i ideš dalje -- dok ta duljina ne postane jednaka 2^n . U tom trenu u b imaš sortiran niz.
HTH,
| raspjevani_opat (napisa): | | jel bi netko bio toliko dobar pa napisao merge sort u pseudo c-u? |
Pa zar to ne postoji u The skripti? 
Ukratko ideja (za polja duljine 2^n ): imaš dva polja, u prvom je u početku početni niz. Sad u drugo pišeš elemente iz prvog, samo ih sad shvatiš kao 2^n lista duljine 1 . I pritom ih mergeaš (vjerujem da osnovni merge znaš napisati, ako ne javi), 2i-tu s (2i+1)-vom. I to pišeš na njima odgovarajuća mjesta u drugom polju. Nakon što napraviš jedan prolaz, prepišeš drugo polje natrag u prvo (puno efikasnije ako imaš pointere na polja da ih samo zamijeniš, no to je već stvar implementacije), i ponavljaš isto s listama duljine 2 . Dakle sad mergeaš (u prethodnom koraku sortirane) (a[0],a[1]) i (a[2],a[3]) u jednu "listu" duljine 4 , i nju pišeš u b[0]..b[3] . Zatim isto s (a[4],a[5]) i (a[6],a[7]) , u b[4]..b[7] , itd. Nakon toga opet povećaš duljine listi u pitanju duplo, zamijeniš polja (ili prepišeš b u a ), i ideš dalje – dok ta duljina ne postane jednaka 2^n . U tom trenu u b imaš sortiran niz.
HTH,
|
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3562)16
Spol: 
Lokacija: /sbin/init
|
| Postano: 22:45 ned, 6. 2. 2005 Naslov: |
|
|
|
Da pokusam pogoditi zasto raspjevni_opat [ :rotfl: ] trazi pseudo-kod ([url=http://degiorgi.math.hr/forum/viewtopic.php?p=22054#22054]clicky[/url]):
[quote="vsego"]Btw, na UuRu su nam ukinuli rekurzije. :cry:[/quote]
Koliko znam, prof. Marusic je to objasnio nakon sto je odlucio preskociti rekurzije, pa pretpostavljam da studenti imaju manjih poteskoca ako to pokushaju sami napisati... :?
Da pokusam pogoditi zasto raspjevni_opat [  ] trazi pseudo-kod (clicky):
| vsego (napisa): | Btw, na UuRu su nam ukinuli rekurzije.  |
Koliko znam, prof. Marusic je to objasnio nakon sto je odlucio preskociti rekurzije, pa pretpostavljam da studenti imaju manjih poteskoca ako to pokushaju sami napisati... 
_________________ U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.  |
|
| [Vrh] |
|
veky
Forumaš(ica)
Pridružen/a: 09. 12. 2002. (19:59:43)
Postovi: (5B0)16
Lokacija: negdje daleko...
|
|
| [Vrh] |
|
ahri
Forumaš(ica)
Pridružen/a: 19. 11. 2003. (23:16:07)
Postovi: (193)16
|
|
| [Vrh] |
|
greeneyes
Forumaš(ica)
Pridružen/a: 13. 09. 2004. (11:44:20)
Postovi: (CD)16
Spol: 
Lokacija: The water's edge Is where she waits
|
| Postano: 10:12 pon, 7. 2. 2005 Naslov: |
|
|
|
pod naslovom *merge sort* iz frendicinih biljeski od prije par godina (sad mi vise nije cudno kak nisam mogla naci u svojima, jer kod nismo izgleda ni napisali :? ) pise otprilike ovo:
[code:1]a[0] a[1] .. a[m] & b[0] b[1] .. b[n] => c[0] c[1] .. c[m+n]
...
ap:=0, bp:=0; cp:=0; //indexi
while ((ap<=m) && (bp<=n))
{
if (a[ap] <= b[bp]
{
c[cp]:=a[ap];
ap:=ap + 1;
}
else
{
c[cp]:=b[bp];
bp:=bp + 1;
}
cp:=cp + 1;
}
while (ap<=m)
{
c[cp]:=a[ap];
cp:=cp + 1;
ap:=ap + 1;
}
while (bp<=n)
{
c[cp]:=b[bp];
cp:=cp + 1;
bp:=bp + 1;
}[/code:1]
ne znam dal ti to kaj pomaze nakon ovog gore strucnog objasnjenja, al barem ne izgleda tolko strashno ;) vjerojatno zato jer je to samo pol kostura svega ;)
btw, mislim da je bitnije skuziti kak to cudo od sorta funkcionira (vekyjev post, a bilo je i na predavanju) nego sam kod koji mi nemamo u biljeskama, pa je onda valjda za ocekivati da ga ne bude trebalo napisati na usmenom;O) druga stvar da to neke ljude stvarno zanima i da bi htjeli kod i znati napisati, ne samo zbog ocjene ;)
[color=blue][b]Moderator:[/b] Dodah code-blok za bolju preglednost.[/color]
pod naslovom *merge sort* iz frendicinih biljeski od prije par godina (sad mi vise nije cudno kak nisam mogla naci u svojima, jer kod nismo izgleda ni napisali ) pise otprilike ovo:
| Kod: | a[0] a[1] .. a[m] & b[0] b[1] .. b[n] => c[0] c[1] .. c[m+n]
...
ap:=0, bp:=0; cp:=0; //indexi
while ((ap<=m) && (bp<=n))
{
if (a[ap] <= b[bp]
{
c[cp]:=a[ap];
ap:=ap + 1;
}
else
{
c[cp]:=b[bp];
bp:=bp + 1;
}
cp:=cp + 1;
}
while (ap<=m)
{
c[cp]:=a[ap];
cp:=cp + 1;
ap:=ap + 1;
}
while (bp<=n)
{
c[cp]:=b[bp];
cp:=cp + 1;
bp:=bp + 1;
} |
ne znam dal ti to kaj pomaze nakon ovog gore strucnog objasnjenja, al barem ne izgleda tolko strashno  vjerojatno zato jer je to samo pol kostura svega
btw, mislim da je bitnije skuziti kak to cudo od sorta funkcionira (vekyjev post, a bilo je i na predavanju) nego sam kod koji mi nemamo u biljeskama, pa je onda valjda za ocekivati da ga ne bude trebalo napisati na usmenom;O) druga stvar da to neke ljude stvarno zanima i da bi htjeli kod i znati napisati, ne samo zbog ocjene
Moderator: Dodah code-blok za bolju preglednost.
_________________
Am I so different from you
Now does it scare you that I'm able to discern
What to love and what to burn..
Don't judge what you don't understand..
// Disturbed: Fear
|
|
| [Vrh] |
|
raspjevani_opat
Forumaš(ica)
Pridružen/a: 04. 02. 2005. (12:42:04)
Postovi: (E5)16
|
|
| [Vrh] |
|
Meri
Forumaš(ica)
Pridružen/a: 11. 11. 2004. (14:48:32)
Postovi: (155)16
Spol:
Lokacija: Zagreb, Zaaaaagreb...tararam...
|
|
| [Vrh] |
|
raspjevani_opat
Forumaš(ica)
Pridružen/a: 04. 02. 2005. (12:42:04)
Postovi: (E5)16
|
|
| [Vrh] |
|
Gost
|
|
| [Vrh] |
|
ahri
Forumaš(ica)
Pridružen/a: 19. 11. 2003. (23:16:07)
Postovi: (193)16
|
|
| [Vrh] |
|
Meri
Forumaš(ica)
Pridružen/a: 11. 11. 2004. (14:48:32)
Postovi: (155)16
Spol:
Lokacija: Zagreb, Zaaaaagreb...tararam...
|
|
| [Vrh] |
|
mdoko
Forumaš(ica)
Pridružen/a: 30. 11. 2002. (22:17:12)
Postovi: (71A)16
Spol:
Lokacija: Heriot-Watt University, Edinburgh
|
|
| [Vrh] |
|
raspjevani_opat
Forumaš(ica)
Pridružen/a: 04. 02. 2005. (12:42:04)
Postovi: (E5)16
|
|
| [Vrh] |
|
Meri
Forumaš(ica)
Pridružen/a: 11. 11. 2004. (14:48:32)
Postovi: (155)16
Spol:
Lokacija: Zagreb, Zaaaaagreb...tararam...
|
|
| [Vrh] |
|
Meri
Forumaš(ica)
Pridružen/a: 11. 11. 2004. (14:48:32)
Postovi: (155)16
Spol:
Lokacija: Zagreb, Zaaaaagreb...tararam...
|
|
| [Vrh] |
|
Ana
Forumaš(ica)
Pridružen/a: 16. 01. 2005. (20:41:07)
Postovi: (89)16
Spol: 
|
|
| [Vrh] |
|
Ana
Forumaš(ica)
Pridružen/a: 16. 01. 2005. (20:41:07)
Postovi: (89)16
Spol:
|
|
| [Vrh] |
|
mdoko
Forumaš(ica)
Pridružen/a: 30. 11. 2002. (22:17:12)
Postovi: (71A)16
Spol:
Lokacija: Heriot-Watt University, Edinburgh
|
|
| [Vrh] |
|
|
i to na onaj njegov nacin (trebas to ili imas?), ne na onaj s vjezbi.. ahem.. a vec budemo mergeal ko veliki kad dodjemo do toga u c-u.. valjda. ;O)
) nadajmo se... 
