Diskuze: Implementace QuickSortu - zhodnocení

Ondřej Krsička

Tvůrce

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

Patrik Valkovič

Tvůrce

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 n². 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.

Ondřej Krsička

Tvůrce

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

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.