Le tri en tas (c'est aussi un tri pyramidal) sur Habré a déjà été rappelé avec un bon mot plus d'une ou deux fois, mais cela a toujours été une information assez connue. Tout le monde connaît le tas binaire habituel, mais la théorie des algorithmes a aussi: unn-tas; un tas de tas basés sur les chiffres de Leonardo; Deramide (un hybride de tas et d'arbre de recherche binaire); mini-pile de tournoi; miroir (inverse); pile faible; Le tas de Jung; tas binomial; et Dieu sait quels autres tas ...Et les représentants les plus intelligents de l'informatique au cours des différentes années ont proposé leurs algorithmes de tri en utilisant ces structures pyramidales. Peu importe ce qu'ils ont fait - pour ceux que nous commençons une petite série d'articles consacrés au tri en utilisant ces structures. Le monde des tas est diversifié - j'espère que vous serez intéressé.
Cet article a été écrit avec le soutien d'EDISON.
Nous sommes engagés dans le développement d'applications mobiles et fournissons des services de test de logiciels .
Nous aimons la théorie des algorithmes! ;-)
Il existe une telle classe d'algorithmes - tri par choix. L'idée générale est que la partie non ordonnée du tableau est réduite du fait qu'il recherche le maximum d'éléments qui en sont réorganisés dans une zone triée croissante.Le tri du choix habituel est la force brute. Si, à la recherche de maxima, il est simple de parcourir linéairement le tableau, alors la complexité temporelle d'un tel algorithme ne peut pas dépasser O ( n 2 ).Un tas
La façon la plus efficace de travailler avec les sommets du tableau consiste à organiser les données dans une arborescence spéciale, appelée segment de mémoire . Il s'agit d'un arbre dans lequel tous les nœuds parents ne sont pas moins que des nœuds descendants.Autres noms du tas - la pyramide , l'arbre de tri .Voyons comment il peut être facile et presque gratuit de présenter un tableau sous la forme d'un arbre.Prenez le tout premier élément du tableau et considérez qu'il s'agit de la racine de l'arbre - un nœud du 1er niveau. Les 2 éléments suivants sont des nœuds du 2e niveau, les descendants droit et gauche de l'élément racine. Les 4 éléments suivants sont des nœuds du 3ème niveau, les descendants droit / gauche du deuxième / troisième élément du tableau. Les 8 éléments suivants sont des nœuds du 4ème niveau, descendants d'éléments du 3ème niveau. Etc. Dans cette image, les nœuds de l'arbre binaire sont clairement situés strictement en dessous des éléments correspondants dans le tableau:Bien que les arbres dans les diagrammes soient plus souvent représentés dans une telle analyse:Si vous regardez cet angle, vous comprendrez pourquoi le tri par groupe est appelé tri pyramidal. Bien que cela soit à peu près la même chose que si vous appelez un éléphant d'échecs un officier, une tour une tura et une reine une reine.Les indices pour les descendants du i- ème élément sont déterminés par élémentaire (si l'indice du premier élément du tableau est considéré comme égal à 0, comme c'est la coutume dans la majorité des langages de programmation):descendant gauche de 2 × i + 1,enfant droit: 2 × i + 2(je suis sur les graphiques et dans les animations, traditionnellement, les index des tableaux commencent par 1, où les formules sont légèrement différentes: enfant gauche: 2 × i et enfant droit: 2 × i + 1, mais ce sont déjà de petites nuances arithmétiques).Si la progéniture résultante de ces formules, les indices dépassent le tableau, cela signifie que le i- ème élément n'a pas d'enfants. Il peut également arriver que le i- ème élément soit un descendant gauche (tombe sur le dernier élément du tableau dans lequel un nombre impair d'éléments), mais il n'y a pas de droite.Ainsi, n'importe quel tableau peut être facilement représenté sous la forme d'un arbre, cependant, ce n'est pas encore un tas, car, dans le tableau, certains éléments descendants peuvent être plus grands que leurs éléments parents.Pour que notre arbre, créé sur la base du tableau, devienne un tas, il doit être tamisé correctement.Tamisage
L'âme du tri d'un groupe est criblante.Le criblage d'un élément est que s'il est plus petit que les descendants combinés dans une chaîne inextricable, alors cet élément doit être déplacé le plus bas possible, et les descendants plus gros doivent être élevés d'un niveau vers le haut.L'image montre le chemin de tamisage de l'article. La couleur bleue indique l'élément pour lequel le tamisage est effectué. Vert - descendants plus gros sur la branche. Ils seront surélevés d'un niveau, car ils sont plus grands que le nœud bleu pour lequel l'écran est fait. L'élément lui-même du nœud bleu le plus haut sera déplacé à l'endroit du descendant le plus bas de la chaîne verte.Un criblage est nécessaire afin de faire un arbre de tri à partir d'un arbre ordinaire et de soutenir davantage l'arbre dans cet état (de tri).Dans cette image, les éléments du tableau sont redistribués de sorte qu'il est déjà disposé en tas. Bien que le tableau soit décomposé en arbre de tri, il n'a pas encore été trié (ascendant ou descendant), bien que tous les descendants de l'arbre soient plus petits que leurs nœuds parents. Mais alors l'élément le plus maximal dans l'arbre de tri est toujours dans la racine principale, ce qui est très important.Tri de tas :: Heapsort
L'algorithme est en fait simple:- Étape 1. Nous formons un arbre de tri à partir de l'ensemble du tableau. Pour ce faire, on passe de droite à gauche les éléments (du dernier au premier) et si l'élément a des descendants, alors on fait un tri.
- 2. . , . ( ) . , .. . , — . , .
Code Python pour une implémentation de tri pyramidal classique:
def HeapSort(data):
for start in range((len(data) - 2) / 2, -1, -1):
HeapSift(data, start, len(data) - 1)
for end in range(len(data) - 1, 0, -1):
data[end], data[0] = data[0], data[end]
HeapSift(data, 0, end - 1)
return data
def HeapSift(data, start, end):
root = start
while True:
child = root * 2 + 1
if child > end: break
if child + 1 <= end and data[child] < data[child + 1]:
child += 1
if data[root] < data[child]:
data[root], data[child] = data[child], data[root]
root = child
else:
break
Complexité de l'algorithme
Pourquoi un simple tas est bon - il n'a pas besoin d'être stocké séparément, contrairement à d'autres types d'arbres (par exemple, un arbre de recherche binaire basé sur un tableau doit être créé avant utilisation). Tout tableau est déjà un arbre dans lequel, en déplacement, vous pouvez immédiatement identifier les parents et les descendants. La complexité de la mémoire supplémentaire est O ( 1 ), tout se passe tout de suite.Quant à la complexité du temps, elle dépend du criblage. Un seul tamisage est contourné en O (log n ) . Tout d'abord, nous faisons un tri pour n éléments afin de construire le tas initial à partir du tableau - cette étape prend O ( n log n ) . À la deuxième étape, lorsque nous sortons nles maximums actuels du tas, nous effectuons un seul tri pour la partie non triée restante, c'est-à-dire cette étape nous coûte aussi O ( n log n ) .Complexité temporelle totale: O ( n log n ) + O ( n log n ) = O ( n log n ).De plus, le tri pyramidal n'a ni cas dégénérés ni meilleurs. Tout tableau sera traité à une vitesse décente, mais il n'y aura ni dégradation ni enregistrement.Le tri en tas est en moyenne légèrement plus lent que le tri rapide. Mais pour le tri rapide, vous pouvez choisir un tableau de tueur sur lequel l'ordinateur se bloque, mais pour le tri sélectif - non.:: Ternary heapsort
Regardons le tas ternaire. Vous ne le croirez pas du binaire, il ne diffère que par le fait que les nœuds parents ont au maximum non pas deux, mais trois descendants. Dans le tas ternaire pour le i -ème code élémentaire, trois descendants sont calculés de manière similaire (si le premier indice d'élément = 0):Le descendant gauche 3 × i + 1Descendant moyen 3 × i + 2descendant droit 3 × i + 3(Si les index commencent par 1, comme dans les animations de cet article, puis dans ces formules il vous suffit d'en soustraire un).Processus de tri:D'une part, le nombre de niveaux dans l'arbre diminue nettement par rapport au tas binaire, ce qui signifie qu'en moyenne, il y aura moins de swaps pendant le tamisage. D'un autre côté, pour trouver le descendant minimum, plus de comparaisons seront nécessaires - parce que les descendants ne sont plus maintenant deux, mais trois chacun. En général, en termes de complexité temporelle - quelque part on trouve, quelque part on perd, mais en général la même chose. Les données du tas ternaire sont triées un peu plus vite que celles du binaire, mais cette accélération est très petite. Dans toutes les variantes du tri pyramidal, les développeurs des algorithmes préfèrent prendre l'option binaire, car le ternaire est censé être plus difficile à implémenter (bien qu'il soit «plus difficile» d'ajouter quelques ou trois lignes supplémentaires à l'algorithme), et le gain de vitesse est minime.Trier par tas n-tas :: N-narny heapsort
Bien sûr, vous ne pouvez pas vous arrêter là et adapter le tri par groupe pour un nombre illimité de descendants. Peut-être que si vous continuez d'augmenter le nombre de descendants, vous pouvez augmenter considérablement la vitesse du processus?Pour le i ème élément des indices du tableau (si le compte de zéro), ses N descendants calculés très simplement:1er descendant: N × i + 12ème descendant: N × i + 23ème descendant: N × i + 3...Nième descendant: N × i + NCode Python pour le tri par un N-tas:
def NHeapSort(data):
n = 3
for start in range(len(data), -1, -1):
NHeapSift(data, n, start, len(data) - 1)
for end in range(len(data) - 1, 0, -1):
data[end], data[0] = data[0], data[end]
NHeapSift(data, n, 0, end - 1)
return data
def NHeapSift(data, n, start, end):
root = start
while True:
child = root * n + 1
if child > end:
break
max = child
for k in range(2, n + 1):
current = root * n + k
if current > end:
break
if data[current] > data[max]:
max = current
if data[root] < data[max]:
data[root], data[max] = data[max], data[root]
root = max
else:
break
Cependant, plus ne signifie pas mieux. Si vous prenez la situation à l'extrême et prenez N descendants pour un tableau de N éléments, le tri par groupe se dégrade en tri par le choix habituel. De plus, ce sera également une version aggravée du tri par sélection, car des gestes insensés seront effectués: le criblage mettra d'abord le maximum en première position dans le tableau, puis il enverra le maximum à la fin (en tri par sélection, le maximum est envoyé immédiatement à la fin).Si le tas ternaire dépasse au minimum le binaire, alors le quadruple perd déjà. Trouver le descendant maximum parmi plusieurs devient trop cher.Remorque de la série suivante
Ainsi, le principal inconvénient du binaire / ternaire / n-tas est l'impossibilité de sauter dans sa complexité est supérieure à O ( n log n ) . Le moyen de sortir de l'impasse est d'utiliser des variétés de tas plus sophistiquées dans le tri. Dans une semaine, nous prendrons connaissance de ce qu'en pense Edsger Dijkstra.Cliquez sur l'animation pour accéder à l'article avec le tri suivant par groupeRéférences
Tas / PyramideArticles de série:
L'application AlgoLab a ajouté le tri par n-tas. Pour sélectionner le nombre de descendants, dans le commentaire sur la cellule de ce type, vous devez spécifier un nombre pour n. La plage de valeurs possibles est de 2 à 5 (cela n'a plus de sens, car pour n> = 6, une animation avec trois niveaux d'imbrication à une échelle normale n'est pas garantie pour tenir sur l'écran).