shell sort c with examples
Technique de tri par shell en C ++: un aperçu complet.
Le tri shell est souvent qualifié d'amélioration par rapport au tri par insertion. Dans le tri par insertion, nous prenons des incréments de 1 pour comparer les éléments et les mettre à leur place.
Dans le tri shell, la liste est triée en la décomposant en plusieurs sous-listes plus petites. Il n’est pas nécessaire que les listes contiennent des éléments contigus. Au lieu de cela, la technique de tri par shell utilise l'incrément i, également appelé «écart», et l'utilise pour créer une liste d'éléments séparés par des éléments «i».
=> Voir ici pour explorer la liste complète des didacticiels C ++.
questions d'entrevue sur maven et jenkins
Ce que vous apprendrez:
Algorithme général
L'algorithme général pour le tri shell est donné ci-dessous.
shell_sort (A, N)
où A - liste à trier; N - taille_espace
définir gap_size = N, flag = 1
tandis que gap_size> 1 ou flag = 1, répétez
commencer
définir l'indicateur = 0
définir gap_size = (gap_size + 1) / 2
finir
pour i = 0 à i<(N-gap_size) repeat
commencer
si A (i + gap_size)> A (i)
swap A (i + gap_size), A (i)
définir l'indicateur = 0
finir
finir
Ainsi, dans l'algorithme ci-dessus, nous définissons d'abord N qui est l'écart pour trier le tableau A en utilisant le tri shell. Dans l'étape suivante, nous divisons le tableau en sous-tableaux en utilisant l'écart. Ensuite, à l'étape suivante, nous trions chacun des sous-tableaux afin qu'à la fin de la boucle, nous obtenions un tableau trié.
Ensuite, considérons un exemple détaillé pour mieux comprendre le tri des coquilles à l'aide d'une représentation picturale.
Illustration
Illustrons le tri Shell avec un exemple.
Considérez le tableau suivant de 10 éléments.
Si nous fournissons un écart de 3, alors nous aurons les sous-listes suivantes avec chaque élément séparé de 3 éléments. Nous trions ensuite ces trois sous-listes.
Les sous-listes triées et la liste résultante que nous obtenons après avoir combiné les trois sous-listes triées sont présentées ci-dessous.
Le tableau ci-dessus que nous avons obtenu après la fusion des sous-tableaux triés est presque trié. Nous pouvons maintenant effectuer un tri par insertion sur cette liste et trier le tableau entier. Cette dernière étape est illustrée ci-dessous pour votre référence.
Comme vu ci-dessus, après avoir effectué le tri shell et fusionné les sous-listes triées, nous n'avons eu besoin que de trois mouvements pour trier complètement la liste. Ainsi, nous pouvons voir que nous pouvons réduire considérablement le nombre d'étapes nécessaires pour trier le tableau.
Le choix de l'incrément pour créer des sous-listes est une caractéristique unique du tri shell.
Exemple C ++
Voyons l'implémentation du tri shell en C ++ ci-dessous.
#include using namespace std; // shellsort implementation int shellSort(int arr(), int N) { for (int gap = N/2; gap > 0; gap /= 2) { for (int i = gap; i = gap && arr(j - gap) > temp; j -= gap) arr(j) = arr(j - gap); arr(j) = temp; } } return 0; } int main() { int arr() = {45,23,53,43,18,24,8,95,101}, i; //Calculate size of array int N = sizeof(arr)/sizeof(arr(0)); cout << 'Array to be sorted:
'; for (int i=0; i Production:
Tableau à trier:
45 23 53 43 18 24 8 95 101
Tableau après tri shell:
8 18 23 24 43 45 53 95 101
Nous avons utilisé la même liste que celle que nous avons utilisée dans l'illustration et nous pouvons voir que nous commençons d'abord par créer deux sous-listes, puis en réduisant davantage l'écart. Une fois que les sous-listes sont créées selon l'écart spécifié, nous trions chacune des sous-listes. Une fois toutes les sous-listes triées, nous obtenons la liste presque triée. Maintenant, cette liste peut être triée en utilisant le tri d'insertion de base qui prendra très peu de mouvements.
Ensuite, implémentons le tri shell en utilisant le langage Java.
Exemple Java
// Java class for ShellSort class ShellSort { //function to sort the array using shell sort int sort(int arr()) { int N = arr.length; // Start with a big gap, then narrow the gap for (int gap = N/2; gap > 0; gap /= 2) { //sort sub lists created by applying gap for (int i = gap; i = gap && arr(j - gap) > temp; j -= gap) arr(j) = arr(j - gap); arr(j) = temp; } } return 0; } } class Main{ public static void main(String args()) { int arr() = {45,23,53,43,18,24,8,95,101}; int N = arr.length; System.out.println('Array to be sorted: '); for (int i=0; i Production:
Tableau à trier:
45 23 53 43 18 24 8 95 101
Tableau après tri shell:
8 18 23 24 43 45 53 95 101
Nous avons implémenté la même logique pour le tri shell dans les programmes C ++ et Java. Ainsi, comme expliqué ci-dessus dans le programme Java, nous divisons d'abord le tableau en sous-tableaux, puis nous les trions pour obtenir un tableau trié complet.
Conclusion
Le tri shell est l'algorithme très efficace qui améliore le tri par insertion.
Alors que le tri par insertion fonctionne en incrémentant ses éléments de 1, le tri par shell utilise le paramètre «gap» pour diviser le tableau en sous-tableaux dont les éléments sont séparés par un «gap». Ensuite, nous pouvons trier la liste individuelle en utilisant le tri par insertion pour obtenir le tableau trié complet.
Le tri Shell est plus rapide que le tri par insertion et prend moins de mouvements pour trier le tableau que le tri par insertion. Notre prochain tutoriel explorera tout sur la technique de tri de tas pour trier les structures de données.
=> Visitez ici pour apprendre le C ++ à partir de zéro.
lecture recommandée
- Sélection de tri en C ++ avec des exemples
- Méthode MongoDB Sort () avec exemples
- Commande de tri Unix avec syntaxe, options et exemples
- Tri à bulles en C ++ avec des exemples
- Tri par insertion en C ++ avec des exemples
- Fusionner le tri en C ++ avec des exemples
- Tri de tas en C ++ avec des exemples
- Tri rapide en C ++ avec des exemples