Tri par insertion

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

• Complexité temporelle : O(n) au mieux si presque trié, O(n²) en moyenne et au pire.
• Complexité spatiale : en place (ne fait que bouger les éléments existants)
• Tri stable
• Utilisé par d'autres implémentations de tris (rapide, par tas) pour "finir" de trier les petits ensembles restants.