Diskusia – Triedenie priamym vkladaním

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.

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

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?

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

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.

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

Já vím co je binární hledání

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.

1.

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 - XsortInsertMid­dle_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.