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

1. 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á.
2. 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.
3. bod 2 opakujeme do konce seznamu(pole).

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

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;                
            }
        }
    }

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;                
            }
        }
    }
 
 
}