NOVINKA: Získej 40 hodin praktických dovedností s AI – ZDARMA ke každému akreditovanému kurzu!
Mezinárodní den IT společnosti je tady! Pouze nyní můžeš získat 90 % extra kreditů při nákupu od 1199 kreditů s promo kódem AJTACI90. Tak neváhej!

Diskuze – Lekce 6 - Quick sort

Zpět

Upozorňujeme, že diskuze pod našimi online kurzy jsou nemoderované a primárně slouží k získávání zpětné vazby pro budoucí vylepšení kurzů. Pro studenty našich rekvalifikačních kurzů nabízíme možnost přímého kontaktu s lektory a studijním referentem pro osobní konzultace a podporu v rámci jejich studia. Toto je exkluzivní služba, která zajišťuje kvalitní a cílenou pomoc v případě jakýchkoli dotazů nebo projektů.

Komentáře
Avatar
Milan Gatyas
Neregistrovaný
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 :-)

 
Odpovědět
29.1.2013 22:08
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).

Odpovědět
30.1.2013 10:05
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? :))

 
Odpovědět
2.6.2013 1:30
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá 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.

Odpovědět
2.6.2013 10:16
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?

Editováno 26.4.2014 21:00
 
Odpovědět
26.4.2014 20:58
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.

 
Odpovědět
31.5.2015 17:16
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.

 
Odpovědět
16.11.2016 13:08
Avatar
Luboš Běhounek Satik
Tvůrce
Avatar
Odpovídá 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.

Editováno 16.11.2016 14:50
Odpovědět
16.11.2016 14:50
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.

 
Odpovědět
29.11.2017 0:28
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.

 
Odpovědět
24.4.2018 16:08
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 10 zpráv z 20.