Diskuze – Lekce 3 - Insertion 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

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.

Odpovědět

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

Odpovědět

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?

Odpovědět

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.

Odpovědět

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.

Odpovědět

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

Odpovědět

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

Odpovědět

1.6.2013 12:19

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

jigfreed

Člen

jigfreed:2.6.2013 1:33

Odpovědět

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.

Odpovědět

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.

Odpovědět

30.6.2017 13:23

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 16.

Nejčastěji vyhledáváné

Diskuze – Lekce 3 - Insertion sort