Avatar
Ondřej Krsička
Redaktor
Avatar
Ondřej Krsička:

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.valkovic
Šéfredaktor
Avatar
Odpovídá na Ondřej Krsička
patrik.valkovic:

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
Redaktor
Avatar
Odpovídá na patrik.valkovic
Ondřej Krsička:

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.