Mikuláš je tu! Získaj 90 % extra kreditov ZADARMO s promo kódom CERTIK90 pri nákupe od 1 199 kreditov. Len do nedele 7. 12. 2025! Zisti viac:
NOVINKA: Najžiadanejšie rekvalifikačné kurzy teraz s 50% zľavou + kurz AI ZADARMO. Nečakaj, táto ponuka dlho nevydrží! Zisti viac:

Diskusia – Quick sort

Späť

Upozorňujeme, že diskusie pod našimi online kurzami sú nemoderované a primárne slúžia na získavanie spätnej väzby pre budúce vylepšenie kurzov. Pre študentov našich rekvalifikačných kurzov ponúkame možnosť priameho kontaktu s lektormi a študijným referentom pre osobné konzultácie a podporu v rámci ich štúdia. Toto je exkluzívna služba, ktorá zaisťuje kvalitnú a cielenú pomoc v prípade akýchkoľvek otázok alebo projektov.

Komentáre
Posledné komentáre sú na spodnej časti poslednej stránky.
Avatar
Milan Gatyas
Nevyplnené
Avatar
Milan Gatyas:29.1.2013 22:08

public static void SeradQuick(object[] s, IComparer c)
{
SeradQuick(s, c, 0, s.Length - 1);
}

private static void SeradQuick(object[] s, IComparer c, int start, int end)
{
if (start >= end)
return;

object median = s[(start + end)/2];
int i = start;
int j = end;

while (i < j)
{
while (c.Compare(s[i], median) < 0)
i++;
while (c.Compare(s[j], median) > 0)
j--;

if (i < j)
{
object temp = s[i];
s[i] = s[j];
s[j] = temp;
i++;
j--;
}
}
if (i == j && c.Compare(median, s[j]) < 0)
j--;
SeradQuick(s, c, start, j);
SeradQuick(s, c, j + 1, end);
}

Podobná verze :-)

Avatar
Kit
Tvůrce
Avatar
Kit:30.1.2013 10:05

Pokud vím, na řazení databází se používají nejčastěji B-stromy, které jsou pro seřazená data velmi efektivní, pro náhodná data také O(n log n) a nemohou spadnout na O(n2).

Odpovedať
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
jigfreed
Člen
Avatar
jigfreed:2.6.2013 1:30

Ahoj, zarazila mě věta "Když něco dělíme na poloviny, složitost bude jistě dvojkový logaritmus, tedy O(log n)." A v závorce je uveden logaritmus desítkový? Nebo si mám opět zopakovat logaritmy? :))

Avatar
David Hartinger
Vlastník
Avatar
Odpovedá na jigfreed
David Hartinger:2.6.2013 10:16

Máš pravdu, že by tam měla být ještě dvojka, někdy to upřesním.

Odpovedať
New kid back on the block with a R.I.P
Avatar
michaela
Člen
Avatar
michaela:26.4.2014 20:58

od 1:47 tomu videu nerozumiem :( preco sa neoddeli 7 a nepracujeme dalej so zvysnymi 3 prvkami?

Editované
Avatar
Filistin
Člen
Avatar
Filistin:31.5.2015 17:16

Mockrát děkuju. Moc mi to pomohlo. Hlavně ten postup s obrázkama na začatku.

Avatar
d.novy
Člen
Avatar
d.novy:16.11.2016 13:08

Když to pustím na pole o velikosti 10000, tak mi to vrací chybu.

Exception in thread "main" java.lang.Stac­kOverflowError
at cz.csobpoj.al­goritmy.tridi­ci.QuickSort.li­mited_quicksor­t(QuickSort.ja­va:78)
at cz.csobpoj.al­goritmy.tridi­ci.QuickSort.li­mited_quicksor­t(QuickSort.ja­va:81)
at cz.csobpoj.al­goritmy.tridi­ci.QuickSort.li­mited_quicksor­t(QuickSort.ja­va:81)
at cz.csobpoj.al­goritmy.tridi­ci.QuickSort.li­mited_quicksor­t(QuickSort.ja­va:81)
at cz.csobpoj.al­goritmy.tridi­ci.QuickSort.li­mited_quicksor­t(QuickSort.ja­va:81)

Tj. zde

int new_pivot = divide(list, left, right, pivot, debug);
// rekurzivni zavolani na obe casti pole
limited_quicksor­t(list, left, new_pivot - 1, debug);
limited_quicksor­t(list, new_pivot + 1, right, debug);

D.

Avatar
Luboš Běhounek Satik
Tvůrce
Avatar
Odpovedá na d.novy
Luboš Běhounek Satik:16.11.2016 14:50

Můžeš buďto zvětšit stack a nebo lepší a čistší řešení je přepsat rekurzi na cyklus.

Editované
Odpovedať
https://www.facebook.com/peasantsandcastles/
Avatar
Lukáš Kún
Člen
Avatar
Lukáš Kún:29.11.2017 0:28

Moje C# verze bez rekurze:

public static T[] QuickSort<T>(T[] pole)
            where T : IComparable<T>
        {
            Random rnd = new Random();

            int[] lims = new int[pole.Length];
            int li = -1;

            lims[++li] = 0;
            lims[++li] = pole.Length - 1;

            while (li > 0)
            {
                int p = lims[li--];
                int l = lims[li--];
                int prv = l;
                int pos = p;

                Swap(pole, pos, rnd.Next(l, p));

                while (l < p)
                {
                    if (pole[l].CompareTo(pole[pos]) == 1)
                        Swap(pole, l, --p);
                    else
                        l++;
                }

                Swap(pole, pos, p);

                if (pos - prv > 1)
                {
                    if (p < pos)
                    {
                        lims[++li] = p + 1;
                        lims[++li] = pos;
                    }
                    if (prv < p)
                    {
                        lims[++li] = prv;
                        lims[++li] = p - 1;
                    }
                }
            }

            return pole;
        }

static void Swap<T>(T[] pole, int i1, int i2)
        {
            T tmp = pole[i1];
            pole[i1] = pole[i2];
            pole[i2] = tmp;
        }

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.

Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:24.4.2018 16:08

Časová složitost - Tady zalezi na kodu algoritmu. Bezny quick sort na O(n*n) pro opacne serazene pole cisel (desc). Cili, mate z nej bubble sort. Pro normalni zamichani je obvykle stejne rychly jako modifikovany merge sort. Mozna o neco rychlejsi.

Posledné komentáre sú na spodnej časti poslednej stránky.
Robíme čo je v našich silách, aby bola tunajšia diskusia čo najkvalitnejšia. Preto do nej tiež môžu prispievať len registrovaní členovia. Pre zapojenie sa do diskusie sa zaloguj. Ak ešte nemáš účet, zaregistruj sa, je to zadarmo.

Zobrazené 10 správy z 20.