FINÁLNÍ VÝPRODEJ KREDITŮ na ITnetwork je tady. Využij poslední šanci a získej až 80 % extra kreditů ZDARMA na náš interaktivní e-learning. Zjisti více:
NOVINKA: Kurz kybernetické bezpečnosti s akreditací MŠMT, nyní již od 0 Kč. Staň se žádaným profesionálem. Zjisti více:
Avatar
Ondřej Krsička
Tvůrce
Avatar
Ondřej Krsička:18.11.2015 21:34

Ahoj, mohli byste mi někdo posoudit, jestli je tato implementace OK? Časová a paměťová složitost (hlavně paměťová..), efektivnost kódu, jestli by něco šlo v kódu zkrátit, alg. zefektivnit, udělat šikovněji... Díky všem.

public static int[] QuickSort(int[] array)
        {
            if (array.Length <= 1)
                return array;

            List<int> list = new List<int>();
            List<int> left = new List<int>();
            List<int> right = new List<int>();
            int pivot = array[array.Length / 2];

            for (int i = 0; i < array.Length; i++)
                if (i != array.Length / 2)
                    if (array[i] >= pivot)
                        right.Add(array[i]);
                    else
                        left.Add(array[i]);

            int[] L = QuickSort(left.ToArray());
            int[] R = QuickSort(right.ToArray());

            list.AddRange(L);
            list.Add(pivot);
            list.AddRange(R);

            return list.ToArray();
        }
 
Odpovědět
18.11.2015 21:34
Avatar
Patrik Valkovič
Člen
Avatar
Odpovídá na Ondřej Krsička
Patrik Valkovič:18.11.2015 21:47

No první věc, která mě napadá, je nepoužívat pole, ale vracet / přijímat rovnou List. Vyhneš se zbytečnému kopírování.
Dále mi příjde, že v samotné podmínce ti chybí závorky u prvního if (nejsem si tím jistý, ale nepřiřadí se "else" k prvnímu ifu?). I kdyby to fungovalo, v rámci lepší čitelnosti, bych ty závorky napsal ;-) To samé pro for :)
Jednu z podmínek si ušetříš tím, že si pivot uložíš externě, a poté jej odstraníš z pole. Nebudeš muset pokaždé kontrolovat, jestli ne neptáš na pivot (ušetřená podmínka).
Minimálně bych to přepsal takhle:

public static List<int> QuickSort(List<int> array)
        {
            if (array.Length <= 1)
                return array;

            List<int> list = new List<int>();
            List<int> left = new List<int>();
            List<int> right = new List<int>();
            int PivotIndex = array.Length / 2;
            int pivot = array[PivotIndex];
            array.RemoveAt(PivotIndex);

            for (int i = 0; i < array.Length; i++)
            {
                    if (array[i] >= pivot)
                        right.Add(array[i]);
                    else
                        left.Add(array[i]);
            }

            list.AddRange(QuickSort(left.ToArray()));
            list.Add(pivot);
            list.AddRange(QuickSort(right.ToArray()));

            return list;
        }

Potom je tady pár věci, pro které bys musel celý kód přepsat.
Může se stát, že budeš mít data na vstupu tak blbě seřazené, že QuickSort bude mít složitost n2. Proto se často používá pouze omezený počet rekurzí, po kterých QuickSort přechází na jiný algoritmus.
Dále často vytváříš Listy. V každé rekurzi 3 další. Pro nejefektivnější algoritmus se používá přístup, kdy existuje pouze jedno pole, se kterým pracuješ. Hodně tím snížíš paměťovou náročnost, ale nevím, jak moc jsi zkušený, a zda si na to troufneš :)

Nahoru Odpovědět
18.11.2015 21:47
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Ondřej Krsička
Tvůrce
Avatar
Odpovídá na Patrik Valkovič
Ondřej Krsička:18.11.2015 22:11

Za tu možnost s jedním polem díky. Vidím to na docela výzvu :D

 
Nahoru Odpovědět
18.11.2015 22:11
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 3 zpráv z 3.