IT rekvalifikácia. Seniorní programátori zarábajú až 6 000 €/mesiac a rekvalifikácia je prvým krokom. Zisti, ako na to!

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

 
Odpovedať
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).

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

 
Odpovedať
2.6.2013 1:30
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ť
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?

Editované 26.4.2014 21:00
 
Odpovedať
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.

 
Odpovedať
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.

 
Odpovedať
16.11.2016 13:08
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é 16.11.2016 14:50
Odpovedať
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.

 
Odpovedať
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.

 
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ý!