NOVINKA - Online rekvalifikační kurz Java programátor. Oblíbená a studenty ověřená rekvalifikace - nyní i online.
NOVINKA – Víkendový online kurz Software tester, který tě posune dál. Zjisti, jak na to!

Diskuze – Lekce 5 - Merge Sort

Zpět

Upozorňujeme, že diskuze pod našimi online kurzy jsou nemoderované a primárně slouží k získávání zpětné vazby pro budoucí vylepšení kurzů. Pro studenty našich rekvalifikačních kurzů nabízíme možnost přímého kontaktu s lektory a studijním referentem pro osobní konzultace a podporu v rámci jejich studia. Toto je exkluzivní služba, která zajišťuje kvalitní a cílenou pomoc v případě jakýchkoli dotazů nebo projektů.

Komentáře
Avatar
nohandle
Neregistrovaný
Avatar
nohandle:21.10.2011 14:41

Kamenem úrazu algoritmu je potřebná pomocná paměť. >> doporučoval bych na okraj zmínit, že je možné manipulovat pouze s pointerem na paměť, kde jsou uloženy hodnoty pole a tak snížit nároky na celkovou paměťovou režii. Otázkou je nakolik chceme používat tento algoritmus v případech kde je pro nás pamět limitujícím faktorem.

 
Odpovědět
21.10.2011 14:41
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na
David Hartinger:21.10.2011 19:01

To je přeci jedno, jestli použijete referenční nebo hodnotový typ, jen přesouváte paměťový problém ze stacku do haldy, ale té paměti bude potřeba stále stejně. To jak je paměť spravována je vlastností jazyka, ne algoritmu. Algoritmus jí vyžaduje stále stejně bez ohledu na to, kam si ji uložím nebo jak se na ni odkazuji.

Odpovědět
21.10.2011 19:01
New kid back on the block with a R.I.P
Avatar
Martin
Neregistrovaný
Avatar
Martin:21.7.2012 15:40

Mám takový menší dotaz :)
Neměl by být na obrázku ta poslední větem už setřízená ? :D

 
Odpovědět
21.7.2012 15:40
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na
David Hartinger:21.7.2012 17:04

Jo, samozřejmě :) Díky, opravil jsem.

Odpovědět
21.7.2012 17:04
New kid back on the block with a R.I.P
Avatar
Petr Nymsa
Tvůrce
Avatar
Petr Nymsa:25.11.2013 19:50

David Hartinger Máš tu menší problém s přetekáním (Chrome)

Odpovědět
25.11.2013 19:50
Pokrok nezastavíš, neusni a jdi s ním vpřed
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na Petr Nymsa
David Hartinger:25.11.2013 20:03

Díky, kouknu na to :)

Odpovědět
25.11.2013 20:03
New kid back on the block with a R.I.P
Avatar
michaela
Člen
Avatar
michaela:26.4.2014 17:12

nie je v tom obrazku chyba (Prubeh)? lebo pole je 5295318 a potom ked sa deli tak je ze 592 a nie 529, druha cast je ok 5318
inak skvele tutorialy k algoritmom, tie videa sa mi moc pacia :)

 
Odpovědět
26.4.2014 17:12
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:30.6.2017 13:01
  1. U slevani bych zkopirovane prvky do druheho pole bud vymazal a nebo dal svetle sedou barvou.
  2. Algoritmu, kdy za serazena pole povazujene jednotlive prvky a pak to jen slevame, bych nezatracoval a mam i kod

http://mlich.zam.slu.cz/…sorting3.htm - 1 sortListMerge_2a

  • pouziva ho Firefox
  • je to stejne rychle jako quicksort
  • pocet porovnani (cmp funkce v kodu) je mensi nez quick-sort
  • u vice vlaknovych procesoru lze docilit 3x vetsi rychlosti nez u linearniho serazeni, protoze uz od zacatku muzete porovnavat 50% prvku naraz
  • algoritmus vraci ukazatel pameti, tudiz neni treba vsechny prvky presouvat do puvodniho pole
  • samozrejme, pro textove retezce je lepsi udelat pole s ukazateli pameti a presouvat ukazatele, az na zaver presunout prvky v poli
  • je mozne to napsat i pres jedno pole, ale cely algoritmus ti pak brzdi schopnosti pc, kdy musis pri presunu prvku u velkych poli cele pole rotovat. viz na me strance XsortListMerge5_1a

3. Urcite bych pridal jako detekci serazenych poli porovnani sousednich policek. Takto lze algoritmus pri serazeni asc / desc hned ukoncit a vrati zpet serazene pole.

4. Mozna by stalo za zminku, ze Tim Sort, v soucastnosti nej algoritmus, pouziva hybrid insert-sort (male pole) + slevani (velke pole)

 
Odpovědět
30.6.2017 13:01
Avatar
Lukáš Kún
Člen
Avatar
Lukáš Kún:6.11.2017 1:32

Moje C# verze bez rekurze:

static T[] MergeSort<T>(T[] pole)
            where T : IComparable<T>
        {
            if (pole.Length < 2)
                return pole;

            T[] buff = new T[pole.Length];
            bool poleDoBuff = true;
            int pp = 1;
            while (pole.Length / pp >= 1)
            {
                T[] poleZ = poleDoBuff ? pole : buff;
                T[] poleDo = poleDoBuff ? buff : pole;

                int bi = 0;
                while (bi < poleDo.Length)
                {
                    int li = bi;
                    int lk = ((li + pp) > poleDo.Length) ? poleDo.Length : (li + pp);
                    int pi = lk;
                    int bk = ((pi + pp) > poleDo.Length) ? poleDo.Length : (pi + pp);

                    while (bi < bk)
                    {
                        if (li == lk)
                            poleDo[bi++] = poleZ[pi++];
                        else if (pi == bk)
                            poleDo[bi++] = poleZ[li++];
                        else
                        {
                            switch (poleZ[li].CompareTo(poleZ[pi]))
                            {
                                case 1:
                                    poleDo[bi++] = poleZ[pi++];
                                    break;
                                case -1:
                                    poleDo[bi++] = poleZ[li++];
                                    break;
                                case 0:
                                    poleDo[bi++] = poleZ[li++];
                                    poleDo[bi++] = poleZ[pi++];
                                    break;
                            }
                        }
                    }
                }
                poleDoBuff = !poleDoBuff;
                pp *= 2;
            }

            return poleDoBuff ? pole : buff;
        }

Testováno celkem dlouho testem generujícím náhodně dlouhá pole s náhodnými čísly - vše prošlo, tak snad by to mělo fungovat. Ovšem nejsem žádný profík, takže kdo ví :D

Případné námitky rád uvítám.

 
Odpovědět
6.11.2017 1:32
Avatar
Patrik Pastor:19.4.2019 21:38

chtel bych se zeptat, zda podminka if (list.length <= 1) //pokud je kazde pole jednoprvkove

by nemohlo by ve while-podmince:

(while list.length <= 1){
..
..
}
merge(list, left, right);

Tedy, neni mi jasne na konci, zda k metode "merge" vubec dojde (kdyz se v rekurzivnim volani deli pole az na 1-prvkova pole, a tu ranu je vyhodi podminka
if (list.length <= 1) return;

Takze kdy vlastne dochazi k tomu slevani, kdyz se to deli na 1-n pole, ale to znici metodu, kdy tedy dojde ke konecnemu slevani? predem diky

 
Odpovědět
19.4.2019 21:38
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 10 zpráv z 16.