Algorithme de tri par insertion

Dans ce didacticiel, vous apprendrez comment fonctionne le tri par insertion. Vous trouverez également des exemples de travail de tri par insertion en C, C ++, Java et Python.

Le tri par insertion fonctionne de la même manière que nous trions les cartes dans notre main dans un jeu de cartes.

Nous supposons que la première carte est déjà triée puis, nous sélectionnons une carte non triée. Si la carte non triée est plus grande que la carte en main, elle est placée à droite sinon, à gauche. De la même manière, d'autres cartes non triées sont prises et mises à leur place.

Une approche similaire est utilisée par le tri par insertion.

Le tri par insertion est un algorithme de tri qui place un élément non trié à sa place appropriée dans chaque itération.

Comment fonctionne le tri par insertion?

Supposons que nous ayons besoin de trier le tableau suivant.

Tableau initial
  1. Le premier élément du tableau est supposé être trié. Prenez le deuxième élément et rangez-le séparément key.
    Comparez keyavec le premier élément. Si le premier élément est supérieur à key, la clé est placée devant le premier élément. Si le premier élément est supérieur à la clé, la clé est placée devant le premier élément.
  2. Maintenant, les deux premiers éléments sont triés.
    Prenez le troisième élément et comparez-le avec les éléments sur sa gauche. Placé juste derrière l'élément plus petit que lui. S'il n'y a pas d'élément plus petit que lui, placez-le au début du tableau. Placez 1 au début
  3. De même, placez chaque élément non trié à sa position correcte. Placez 4 derrière 1 Placez 3 derrière 1 et le tableau est trié

Algorithme de tri par insertion

 insertionSort (array) marque le premier élément comme trié pour chaque élément non trié X 'extrait' l'élément X pour j X déplace l'élément trié vers la droite de 1 boucle de rupture et insère X ici fin insertionSort

Exemples Python, Java et C / C ++

Python Java C C ++ 
 # Insertion sort in Python def insertionSort(array): for step in range(1, len(array)): key = array(step) j = step - 1 # Compare key with each element on the left of it until an element smaller than it is found # For descending order, change keyarray(j). while j>= 0 and key < array(j): array(j + 1) = array(j) j = j - 1 # Place key at after the element just smaller than it. array(j + 1) = key data = (9, 5, 1, 4, 3) insertionSort(data) print('Sorted Array in Ascending Order:') print(data)
  // Insertion sort in Java import java.util.Arrays; class InsertionSort ( void insertionSort(int array()) ( int size = array.length; for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (j>= 0 && key < array(j)) ( array(j + 1) = array(j); --j; ) // Place key at after the element just smaller than it. array(j + 1) = key; ) ) // Driver code public static void main(String args()) ( int() data = ( 9, 5, 1, 4, 3 ); InsertionSort is = new InsertionSort(); is.insertionSort(data); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
 // Insertion sort in C #include // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( printf("%d ", array(i)); ) printf(""); ) void insertionSort(int array(), int size) ( for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (key = 0) ( array(j + 1) = array(j); --j; ) array(j + 1) = key; ) ) // Driver code int main() ( int data() = (9, 5, 1, 4, 3); int size = sizeof(data) / sizeof(data(0)); insertionSort(data, size); printf("Sorted array in ascending order:"); printArray(data, size); )
 // Insertion sort in C++ #include using namespace std; // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( cout << array(i) << " "; ) cout << endl; ) void insertionSort(int array(), int size) ( for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (key = 0) ( array(j + 1) = array(j); --j; ) array(j + 1) = key; ) ) // Driver code int main() ( int data() = (9, 5, 1, 4, 3); int size = sizeof(data) / sizeof(data(0)); insertionSort(data, size); cout << "Sorted array in ascending order:"; printArray(data, size); )

Complexité

Complexités temporelles

  • Pire complexité des cas: supposons qu'un tableau soit dans l'ordre croissant et que vous souhaitiez le trier par ordre décroissant. Dans ce cas, la complexité du pire des cas se produit. Chaque élément doit être comparé à chacun des autres éléments afin que, pour chaque nième élément, un certain nombre de comparaisons soient effectuées. Ainsi, le nombre total de comparaisons =O(n2)

    (n-1)
    n*(n-1) ~ n2
  • Meilleure complexité des cas: O(n)
    lorsque le tableau est déjà trié, la boucle externe s'exécute nplusieurs fois alors que la boucle interne ne s'exécute pas du tout. Donc, il n'y a qu'un nnombre de comparaisons. Ainsi, la complexité est linéaire.
  • Complexité moyenne des cas: cela se produit lorsque les éléments d'un tableau sont dans un ordre confus (ni croissant ni décroissant).O(n2)

Complexité spatiale

La complexité de l'espace est O(1)due au fait qu'une variable supplémentaire keyest utilisée.

Applications de tri par insertion

Le tri par insertion est utilisé lorsque:

  • le tableau contient un petit nombre d'éléments
  • il ne reste plus que quelques éléments à trier

Articles intéressants...