Diskusia – Triedenie priamym vkladaním

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

Mircosoft

Tvůrce

Mircosoft:21.7.2011 10:08

Výhoda insertsortu je, že se dá celkem jednoduše použít i na seznamy, které teprve vytváříme - třeba když uživatel zadává slova a program je má průběžně ukládat v abecedním pořadí. Pak to, co už máme, považujeme za setříděnou část, a nesetříděnou část představuje jenom ta jedna zadaná hodnota.

Odpovedať

21.7.2011 10:08

David Hartinger

Vlastník

David Hartinger:21.7.2011 10:19

Nad tím jsem nikdy nepřemýšlel, je to jistě dobrá vlastnost

Odpovedať

21.7.2011 10:19

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

jigfreed

Člen

jigfreed:31.5.2013 16:16

Místo "držení" prvku v paměti by přece šlo oba prvky prohodit, tak jako se tomu děje u bublinkové a selection sortu, nebo je v tom nějakej problém?

Odpovedať

31.5.2013 16:16

Luboš Běhounek Satik

Tvůrce

Luboš Běhounek Satik:31.5.2013 17:04

Drobnou upravou se da dostat slozitost na n*log2n, staci pri hledani, kam prvek zaradime, pouzit binarni puleni.

Odpovedať

31.5.2013 17:04

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

David Hartinger

Vlastník

David Hartinger:1.6.2013 11:40

Myslím, že tu je dostatečně popsané jak to funguje Při prohození si prvek uložíš také do paměti, nevím, v čem je rozdíl.

Odpovedať

1.6.2013 11:40

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

Luboš Běhounek Satik

Tvůrce

Luboš Běhounek Satik:1.6.2013 12:08

Ze kdyz hledas, kam prvek zaradit, tak nejedes prvek po prvku, ale binarnim pulenim hledas, kam ten prvek prijde - podobne jako treba kdyz hadas nahodne cislo od 0-100, tak ti vzdy staci asi 8 pokusu, abys to uhad, nemusis prochazet vsechny cisla postupne

Odpovedať

1.6.2013 12:08

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

David Hartinger

Vlastník

David Hartinger:1.6.2013 12:19

Já vím co je binární hledání ;-)

Odpovedať

1.6.2013 12:19

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

jigfreed

Člen

jigfreed:2.6.2013 1:33

Odpovedať

2.6.2013 1:33

Neaktivní uživatel

Tvůrce

Neaktivní uživatel:10.1.2017 18:46

Optimalizovaný insertion sort pre PHP:

function insertionDesc($input) {

    $arrayLength = sizeof($input);

    $j = 1;
    while($j < $arrayLength) {

        $key = $input[$j];
        $i = $j - 1;

        while($i > -1) {

            if($input[$i] < $key) {

                $input[$i + 1] = $input[$i];
                $input[$i] = $key;
                --$i;

            } else break;

        }

        ++$j;

    }

    return $input;

}

Pre opačné poradie stačí prehodiť podmienku.

Odpovedať

10.1.2017 18:46

Neaktivní uživatelský účet

Peter Mlich

Člen

Peter Mlich:30.6.2017 13:23

Js kod - je to trosku slozitejsi, protoze to kopiruji z testvaciho scriptu

function sortInsert_1a(cmp,start,end)
{
//arr[1] = [6,5,4,3,2,1]
var cycles = 0;
var start = typeof(start)=='undefined' ? 0         : start;
var end   = typeof(end)  =='undefined' ? arr_count : end;
//alert([start, end])
var i,j, tmp;
    for (i=start+1; i<end; i++) // dulezite je pouzit promennou, pole.lenght by kontroloval v kazdem cyklu
        {
        tmp = arr[1][i];
        j = i-1;
        while (j>=start && cmp(arr[1][j],tmp)>0) // cmp porovnava dve cisla, vraci 1, -1, 0; soucasne loguje log_cmp++
           {
            arr[1][j+1] = arr[1][j];
            j--;
cycles++;
           }
        arr[1][j+1] = tmp;
        }
mm.data.cycles[mm.data.i] += cycles; // log_cycles++
return 1;
}

2. Mozna bych doplnil, ze pro vkladani je mozne polohu urcovat jako stred leve a prave strany, mid = left + (right-left>>1). Tim se stane z inserts-rtu algoritmus s nejmensim poctem cmp operaci. A pouziva to hybrid Tim sort.

        mid_sub = right - left;
        while (true)
                {
                cycles++;
                mid = left + (mid_sub>>1);
                if (cmp(arr[m][j],arr[m][mid])>=0)
                        {
                        left  = mid;
                        mid_sub = right - left;
                        if (mid_sub==1) {mid++; break;}
                        }
                else    {
                        right = mid;
                        mid_sub = right - left;
                        if (mid_sub==1) {break;}
                        }
                }
// tady je zas vyhodnejsi pouzit if-else kvuli rychlosti. procesor nemusi skakat v pameti a ukonci to primo v ifu.

http://mlich.zam.slu.cz/…sorting3.htm - XsortInsertMiddle_1a...

3. hlavni problem toho algoritmu je, ze se prvek vklada do stale vetsiho pole a cele se musi posunovat. Coz pc nezvladaji. Proto to Timsort kombinuje se slevanim. Jinak lepsi algoritmus neni.

Odpovedať

30.6.2017 13:23

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 – Triedenie priamym vkladaním