Dans cet article, je voudrais présenter un exemple d'implémentation en Python 3 sur l'algorithme que j'ai appris en lisant "Algorithm Picture Book". L'algorithme cette fois est le tri de tas. L'écrivain est un amateur. J'apprécierais que vous me disiez diverses choses.
Je ne suis pas familier avec Python2, mais je sais seulement que j'utilise Python3 (Est-ce Python3.6.0?). Par conséquent, le titre de l'article est Python3.
Je n'expliquerai que brièvement le problème et l'approche. Nous utilisons une structure de données appelée "tas". Pour plus de détails sur le tas, reportez-vous à "Algorithm Picture Book".
Renvoie les colonnes triées par ordre croissant pour un nombre donné de colonnes.
Exemple: 5, 2, 7, 3, 6, 1, 4 → 1, 2, 3, 4, 5, 6, 7
Stockez le nombre donné dans le tas décroissant (racine maximale), et répétez "Prendre la valeur de la racine-> mettre le plus à gauche". Pour plus de détails, reportez-vous à "Algorithm Picture Book".
Le code implémenté est illustré ci-dessous. Tout d'abord, je vais vous expliquer une petite idée.
De plus, j'ai osé l'implémenter pour étude, mais il semble que Python ait un module appelé heapq dans la bibliothèque standard, donc je pense qu'il est bon de l'utiliser pratiquement (https: //docs.python) .org / ja / 3 / bibliothèque / heapq.html).
Une structure de données appelée tas est réalisée en prenant la signification dans l'ordre des éléments du tableau. Il sera plus facile à comprendre si vous regardez le supplément dans la section de tri de tas du "Livre d'images de l'algorithme".
De plus, dans le tas (tas de 2 minutes), il est pratique de démarrer le numéro d'élément à partir de 1, alors faites-le (tas de deux minutes Wikipedia #implementation of heap % 8C% E5% 88% 86% E3% 83% 92% E3% 83% BC% E3% 83% 97 #% E3% 83% 92% E3% 83% BC% E3% 83% 97% E3% 81% AE% E5% AE% 9F% E8% A3% 85))).
En gros, cela ressemble à ce qui suit.
La liste qui est initialement affectée aux données variables est la colonne numérique à traiter.
De plus, ce code peut être déroutant, je vais donc ajouter quelques fonctions à la version (?) Du code en bas pour une meilleure visibilité. Nous vous serions reconnaissants si vous pouviez nous donner votre avis sur lequel est le meilleur.
heap_sort.py
data = [5, 2, 7, 3, 6, 1, 4]
print("input :" + str(data))
data_len = len(data)
heap = [0] #Le 0ème élément est un mannequin(Il est facile de calculer si on compte à partir de 1 dans le tas)
#Stockez les données d'entrée dans le tas dans l'ordre(Reconstruisez le tas à chaque fois)
for i in range(0, data_len):
heap.append(data[i])
if i > 0:
child = i + 1
parent = child // 2
while(heap[parent] < heap[child]):
heap[parent], heap[child] = heap[child], heap[parent]
if parent > 1:
child = parent
parent = child // 2
else:
#Il a atteint la racine, donc je vais quitter ici
break
#Récupérer les valeurs à la racine du tas(Reconstruisez le tas à chaque fois)
output_data = list() #Tableau pour la sortie
for i in range(0, data_len):
#Copier la valeur racine
output_data.insert(0, heap[1])
#Supprimer les valeurs racine et reconstruire le tas
heap[1] = heap[-1]
heap.pop(-1)
parent = 1
while(len(heap) >= 2 * parent + 1):
if len(heap) == 2 * parent + 1:
if heap[parent] < heap[2 * parent]:
heap[parent], heap[2 * parent] = heap[2 * parent], heap[parent]
#Il n'y a pas de branches au-delà de ça, donc ça sortira
break
else:
if heap[2 * parent] > heap[2 * parent + 1]:
child = 2 * parent
else:
child = 2 * parent + 1
if heap[parent] < heap[child]:
heap[parent], heap[child] = heap[child], heap[parent]
parent = child
else:
break
print("output :" + str(output_data))
python
$ python heap_sort.py
input :[5, 2, 7, 3, 6, 1, 4]
output :[1, 2, 3, 4, 5, 6, 7]
Si vous avez des questions, veuillez les signaler et poser des questions. Surtout s'il y a des améliorations dans la façon d'écrire le code, je pense que ce sera utile pour étudier.
En outre, j'apprécierais des conseils sur le test du code d'implémentation et la comparaison de la vitesse avec d'autres algorithmes. (Je ne l'ai pas encore testé (^^;)
C'est la version (?) Du code ci-dessus qui a amélioré la visibilité en définissant certaines fonctions.
heap_sort_2.py
def parent_of(child):
return child // 2
def left_child_of(parent):
return 2 * parent
def right_child_of(parent):
return 2 * parent + 1
def heap_size(heap):
return len(heap[1:])
data = [5, 2, 7, 3, 6, 1, 4]
# data = [43, 1, -4, 91, 46, -609]
print("input :" + str(data))
data_len = len(data)
heap = [0] #Le 0ème élément est un mannequin(Il est facile de calculer si on compte à partir de 1 dans le tas)
#Stockez les données d'entrée dans le tas dans l'ordre(Reconstruisez le tas à chaque fois)
for i in range(0, data_len):
heap.append(data[i])
if i > 0:
child = i + 1
parent = parent_of(child)
while(heap[parent] < heap[child]):
heap[parent], heap[child] = heap[child], heap[parent]
if parent > 1:
child = parent
parent = parent_of(child)
else:
#Il a atteint la racine, donc je vais quitter ici
break
#Récupérer les valeurs à la racine du tas(Reconstruisez le tas à chaque fois)
output_data = list() #Tableau pour la sortie
for i in range(0, data_len):
#Copier la valeur racine
output_data.insert(0, heap[1])
#Supprimer les valeurs racine et reconstruire le tas
heap[1] = heap[-1]
heap.pop(-1)
parent = 1
while(heap_size(heap) >= left_child_of(parent)):
if heap_size(heap) == left_child_of(parent):
child = left_child_of(parent)
if heap[parent] < heap[child]:
heap[parent], heap[child] = heap[child], heap[parent]
#Il n'y a pas de branches au-delà de ça, donc ça sortira
break
else:
if heap[left_child_of(parent)] > heap[right_child_of(parent)]:
child = left_child_of(parent)
else:
child = right_child_of(parent)
if heap[parent] < heap[child]:
heap[parent], heap[child] = heap[child], heap[parent]
parent = child
else:
break
print("output :" + str(output_data))
Recommended Posts