Tri par insertion

Insertion sort.

Besoin

Trier un ensemble de données petit ou presque trié.

Analyse

Tri à bulle amélioré : Parcourir les éléments et les insérer là où ils doivent êntre dans les précédents déjà triés.

Implémentation

public static void insertionSort(int array[]) {
  for (int currentPos = 1; currentPos < array.length; currentPos++) {   // Start at 2nd element   
    int key = array[currentPos];
    int rightKeyPos = currentPos;
    while (rightKeyPos > 0 && array[rightKeyPos - 1] > key) {           // Bubble down         
      array[rightKeyPos] = array[rightKeyPos - 1];
      rightKeyPos--;
    }        
    array[rightKeyPos] = key;
  }
}

Notes