Diskusia – Merge Sort

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.

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.

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

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

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

Díky, kouknu na to

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

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)

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í

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

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