Introduction au tri en tas en C ++
Heapsort est l'une des techniques de tri basées sur la comparaison et fait partie du tri par sélection. Où le tri est défini comme l'organisation des ensembles de données dans un ordre spécifique en utilisant une valeur unique connue comme un élément clé dans la liste donnée. Le terme tri a été introduit au fur et à mesure que les gens apprenaient l'importance de rechercher n'importe quel élément dans un ensemble d'informations donné, sinon il serait très difficile de rechercher un enregistrement s'il n'était pas ordonné et non trié.
Il existe de nombreuses techniques différentes impliquées dans le tri, chacune ayant son efficacité respective dans le temps nécessaire pour trier les données données et les besoins d'espace en mémoire. Il s'agit du tri à bulles, du tri par insertion, du tri par sélection, du tri rapide, du tri par fusion et du tri par segment.
Qu'est-ce que Heap Sort?
Heapsort est une approche de tri basée sur la structure de données de tas binaire similaire au tri de sélection où nous obtenons d'abord le maximum de données et le plaçons à la fin et continuons pour le reste des éléments.
Heapsort comme son nom l'indique. Il crée d'abord le tas d'éléments de données à partir du tableau non trié donné, puis vérifie le plus grand élément et le place à la fin du tableau partiellement trié. Il reconstruit à nouveau le tas, recherche le prochain plus grand morceau d'enregistrement et le place dans le prochain emplacement vide à partir de la fin de l'arrangement à moitié trié des enregistrements. Ce processus est répété jusqu'à ce qu'il ne reste aucun élément dans le tas. Cette technique nécessite deux tableaux, un pour stocker le tas et l'autre pour un tableau trié.
Algorithme de tri de tas en C ++
- Choisissez d'abord root comme élément élevé dans l'ensemble d'informations donné pour créer un tas maximal.
- Reconstruisez le tas en plaçant ou en échangeant la racine avec le dernier élément.
- La taille du segment de mémoire diminue désormais de 1.
- Ensuite, nous faisons à nouveau le tas avec les éléments restants et continuons jusqu'à ce que la taille du tas soit réduite à 1.
Exemple de tri en tas en C ++
Cette technique utilise un tas binaire qui est construit à l'aide d'un arbre binaire complet où le nœud racine est supérieur à ses deux nœuds enfants.
Considérez le tableau donné d'ensembles de données.
Allons selon l'algorithme. Il dit de sélectionner l'élément le plus élevé comme racine et de construire le tas maximal.
1. Première itération
Maintenant, le tableau sera de la forme:
Maintenant, le tableau trié sera de la forme:
La taille du tas sera réduite de 1, maintenant 6-1 = 5.
2. Deuxième itération
Alors maintenant, le tas ressemble à:
Le tableau est de la forme:
Le tableau trié sera:
La taille du tas sera réduite de 1, maintenant 5-1 = 4.
3. Troisième itération
Le nouveau tas ressemble à:
Le tableau est de la forme:
Le tableau trié sera:
La taille du tas sera réduite de 1, maintenant 4-1 = 3.
4. Quatrième itération
Le nouveau tas ressemble à:
Le tableau est de la forme:
Le tableau trié sera:
La taille du tas sera réduite de 1, maintenant 3-1 = 2.
5. Cinquième itération
Le nouveau tas ressemble à:
Le tableau est de la forme:
Le tableau trié sera:
La taille du tas sera réduite de 1, maintenant 2-1 = 1.
6. Dernière itération
Le nouveau tas ressemble à:
Le tableau a:
4
À partir de l'algorithme, nous avons effectué toutes les étapes jusqu'à ce que la taille du tas soit 1. Nous avons donc maintenant le tableau trié:
Par conséquent, le tableau trié du tas maximal est en ordre croissant. Si nous avons besoin du tableau trié par ordre décroissant, suivez les étapes ci-dessus avec un tas minimal.
Le programme C ++ pour le tri de tas est comme indiqué ci-dessous:
#include
using namespace std;
void heapify(int arr(), int n, int i)
(
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l arr(largest))
largest = l;
if (r arr(largest))
largest = r;
if (largest != i) (
swap(arr(i), arr(largest));
heapify(arr, n, largest);
)
)
void heapSort(int arr(), int n)
(
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i >= 0; i--)
(
swap(arr(0), arr(i));
heapify(arr, i, 0);
)
)
void printArray(int arr(), int n)
(
for (int i = 0; i < n; ++i)
cout << arr(i) << " ";
cout << "\n";
)
int main()
(
int arr() = ( 5, 18, 4, 13, 10, 7);
int n = sizeof(arr) / sizeof(arr(0));
heapSort(arr, n);
cout << "Sorted array is \n";
printArray(arr, n);
)
Production:
Conclusion
Heapsort est la technique basée sur la comparaison qui est l'amélioration du tri par sélection. Le tri de tas utilise la sélection de l'élément le plus élevé ou le plus bas dans le tableau donné pour trier dans l'ordre croissant ou décroissant respectivement avec le tas maximal ou minimal. Effectuez ce processus jusqu'à ce que nous en obtenions un comme taille de segment de mémoire. Cette technique de tri est également utilisée pour trouver l'élément le plus grand et le plus bas du tableau. La technique de tri en tas est plus efficace et plus rapide que la technique de tri par sélection.
Articles recommandés
Ceci est un guide de tri de tas en C ++. Nous discutons ici de ce qu'est le tri en tas en c ++, en travaillant avec son algorithme et son exemple. Vous pouvez également consulter les articles suivants pour en savoir plus-
- Tri en tas en C
- Tri de tas en Java
- Surcharge en C ++
- Pointeurs en C ++
- Surcharge en Java