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

Nejnovější komentáře jsou na konci poslední stránky.

Milan Gatyas

Neregistrovaný

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

Kit

Tvůrce

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

Odpovědět

Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.

jigfreed

Člen

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

David Hartinger

Vlastník

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

New kid back on the block with a R.I.P

michaela

Člen

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

Filistin

Člen

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

d.novy

Člen

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.StackOverflowError
at cz.csobpoj.algoritmy.tridici.QuickSort.limited_quicksort(QuickSort.java:78)
at cz.csobpoj.algoritmy.tridici.QuickSort.limited_quicksort(QuickSort.java:81)
at cz.csobpoj.algoritmy.tridici.QuickSort.limited_quicksort(QuickSort.java:81)
at cz.csobpoj.algoritmy.tridici.QuickSort.limited_quicksort(QuickSort.java:81)
at cz.csobpoj.algoritmy.tridici.QuickSort.limited_quicksort(QuickSort.java:81)

Tj. zde

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

Odpovědět

Luboš Běhounek Satik

Tvůrce

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

https://www.facebook.com/peasantsandcastles/

Lukáš Kún

Člen

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í

Případné námitky rád uvítám.

Odpovědět

Peter Mlich

Člen

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

Nejnovější komentáře jsou na konci poslední stránky.

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.

Nejčastěji vyhledáváné

Diskuze – Lekce 6 - Quick sort