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

Milan Gatyas

Nevyplnené

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 :-)

Odpovedať

29.1.2013 22:08

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

Odpovedať

30.1.2013 10:05

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? :))

Odpovedať

2.6.2013 1:30

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.

Odpovedať

2.6.2013 10:16

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?

Editované 26.4.2014 21:00

Odpovedať

26.4.2014 20:58

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.

Odpovedať

31.5.2015 17:16

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);

Odpovedať

16.11.2016 13:08

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.

Editované 16.11.2016 14:50

Odpovedať

16.11.2016 14:50

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.

Odpovedať

29.11.2017 0:28

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.

Odpovedať

24.4.2018 16:08

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.

Zatiaľ nikto nevložil komentár - buď prvý!

Najčastejšie vyhľadávané

Diskusia – Quick sort