====== InsertSort - řazení vkládáním ======

===== Princip =====
  - začínáme vždy od druhého prvku seznamu(pole), eventuelně předpokládáme, že předchozí část seznamu(pole) je setřízená. 
  - následující prvek zařadíme do již setřízené posloupnosti na správné místo - postupujeme odzadu a větší hodnoty posouváme.
  - bod 2 opakujeme do konce seznamu(pole).   

===== Složitost =====
Asymptotická složitost InsertSort je O(n²), průměrná složitost je n²/4 a v nejlepším případě je dokonce lineární. Je efektivnější než většina O(n²) algoritmů.

===== Řešení =====
<code java>
static void InsertSort (int[] npole)
    {
        int i;                  //index v poli
        int j;                  //index v poli
        int prvek;              //aktualne zpracovavany prvek
        
        for (i=1;i<npole.length;i++)          //vnejsi smycka
        {
            prvek=npole[i];
            for(j=i-1;j>=0&&npole[j]>prvek;j--) //vnitrni smycka - zarazujeme prvek
            {
                npole[j+1]=npole[j];
                npole[j]=prvek;                
            }
        }
    }
</code>

===== Souhrnný ukázkový příklad =====

<code java>
package trideniI;
public class Main {
    public static void main(String[] args) {
        int[] pole = {4,3,2,1};         //nestridene pole
        int index;                      //index pro pruchod pri vypisu
        
        InsertSort(pole);
        for (index=0;index<pole.length;index++)
        {
            System.out.print(pole[index]+" ");
        }
        
        

    }
    static void InsertSort (int[] npole)
    {
        int i;                  //index v poli
        int j;                  //index v poli
        int prvek;              //aktualne zpracovavany prvek
        
        for (i=1;i<npole.length;i++)          //vnejsi smycka
        {
            prvek=npole[i];
            for(j=i-1;j>=0&&npole[j]>prvek;j--) //vnitrni smycka - zarazujeme prvek
            {
                npole[j+1]=npole[j];
                npole[j]=prvek;                
            }
        }
    }
    
    
}
</code>