Le tri Shell est principalement une variante du tri par insertion . Dans le tri par insertion, nous ne déplaçons les éléments que d'une position vers l'avant. Lorsqu'un élément doit être déplacé loin devant, de nombreux mouvements sont nécessaires. L'idée de ShellSort est de permettre l'échange d'objets éloignés. Dans le tri Shell, nous rendons le tableau h-trié pour une grande valeur de h. Nous continuons à réduire la valeur de h jusqu'à ce qu'elle devienne 1. Un tableau est dit h-trié si toutes les sous-listes de chaque h'ième élément sont triées.
Algorithme:
Étape 1 - Démarrer
Étape 2 - Initialiser la valeur de la taille de l'écart. Exemple : h
Étape 3 − Divisez la liste en sous-parties plus petites. Chacun doit avoir des intervalles égaux à h
Étape 4 - Triez ces sous-listes en utilisant le tri par insertion
Étape 5 - Répétez cette étape 2 jusqu'à ce que la liste soit triée.
Étape 6 – Imprimez une liste triée.
Étape 7 - Arrêtez.
Pseudo-code :
PROCEDURE SHELL_SORT(TABLEAU, N)
WHILE GAP < LENGTH(ARRAY) /3 :
GAP = ( INTERVAL * 3 ) + 1
END WHILE LOOP
WHILE GAP > 0 :
FOR (OUTER = GAP; OUTER < LENGTH(ARRAY); OUTER++):
INSERTION_VALUE = TABLEAU[EXTÉRIEUR]
INTÉRIEUR = EXTÉRIEUR ;
WHILE INNER > GAP-1 AND ARRAY[INNER – GAP] >= INSERTION_VALUE:
ARRAY[INNER] = ARRAY[INNER – GAP]
INNER = INNER – GAP
END WHILE LOOP
ARRAY[INNER] = INSERTION_VALUE
END FOR LOOP
GAP = (GAP - 1) /3 ;
FIN WHILE BOUCLE
FIN SHELL_SORT
Voici l'implémentation de ShellSort.
int shellSort(int arr[], int n){ // Start with a big gap, then reduce the gap for (int gap = n/2; gap > 0; gap /= 2) { // Do a gapped insertion sort for this gap size. // The first gap elements a[0..gap-1] are already in gapped order // keep adding one more element until the entire array is // gap sorted for (int i = gap; i < n; i += 1) { // add a[i] to the elements that have been gap sorted // save a[i] in temp and make a hole at position i int temp = arr[i]; // shift earlier gap-sorted elements up until the correct // location for a[i] is found int j; for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) arr[j] = arr[j - gap]; // put temp (the original a[i]) in its correct location arr[j] = temp; } } return 0;} void printArray(int arr[], int n){ for (int i=0; i<n; i++) cout << arr[i] << " ";} int main(){ int arr[] = {12, 34, 54, 2, 3}, i; int n = sizeof(arr)/sizeof(arr[0]); cout << "Array before sorting: \n"; printArray(arr, n); shellSort(arr, n); cout << "\nArray after sorting: \n"; printArray(arr, n); return 0;}Production:
Tableau avant tri : 12 34 54 2 3 Tableau après tri : 2 3 12 34 54
Complexité temporelle : la complexité temporelle de l'implémentation ci-dessus du tri Shell est O(n 2 ). Dans l'implémentation ci-dessus, l'écart est réduit de moitié à chaque itération. Il existe de nombreuses autres façons de réduire les écarts, ce qui conduit à une meilleure complexité temporelle. Voir ceci pour plus de détails.
Complexité
du pire cas La complexité du pire cas pour le tri shell est O(n2)
. Complexité du meilleur cas
Lorsque la liste de tableaux donnée est déjà triée, le nombre total de comparaisons de chaque intervalle est égal à la taille du tableau donné.
La complexité du meilleur cas est donc Ω(n log)
Complexité moyenne des cas
La complexité moyenne des cas du tri shell dépend de l'intervalle sélectionné par le programmeur.
θ(n log2).
LA Complexité moyenne par cas : O(n*log n)
Complexité spatiale
La complexité spatiale de la sorte shell est O(1).
Applications de tri Shell
1. Remplacement du tri par insertion, où il faut beaucoup de temps pour terminer une tâche donnée.
2. Pour appeler la surcharge de la pile, nous utilisons le tri shell.
3. lorsque la récursivité dépasse une limite particulière, nous utilisons le tri shell.
4. Pour les ensembles de données de taille moyenne à grande.
5. En tri par insertion pour réduire le nombre d'opérations.