Les débutants en Python organisent des tris de tas

Ceci est un mémorandum

Je n'y ai pas touché du tout depuis que j'ai les informations de base, alors qu'en est-il du tri en tas? J'ai pensé que je prendrais des notes tout en organisant mes connaissances.

~~ Pakuru ~~ Je vais citer

Il n'est pas impossible de créer un algorithme à partir de zéro, mais honnêtement, c'est difficile, alors je l'ai cité sur le site [Reference: A] et moi-même. Je vais l'organiser en le démontant avec.

Qu'est-ce que le tri par tas en premier lieu?

J'ai écrit les règles générales avec une image heap.png ~~ Je ne sais pas pourquoi j'ai pensé à une chose aussi compliquée, mais ~~ Il semble qu'il soit facile de faire fonctionner de haut en bas en raison du fonctionnement de l'arrangement. Il semble que la structure arborescente soit également utilisée dans Oracle DB (rappelez-vous), et l'efficacité de la recherche de données semble bonne.

Je l'ai écrit dans une note spéciale parce que je pense qu'il y a trois points à retenir.

Corps

Une fonction du corps de tri de tas. Si vous mettez un tableau comme argument ici, il sera trié

heap_sort.py


def heap_sort(array):
    i = 0
    n = len(array)
    #Configurer le tas
    while(i < n):
        upheap(array, i)
        i += 1
    while(i > 1):#De n à 0
        #Récupérer la valeur maximale du tas
        i -= 1
        array[0] , array[i] = array[i] , array[0]
        
        #Reconstruire le tas
        downheap(array, i-1)

Lorsque vous recevez le tableau, définissez la longueur et l'index (comme d'habitude).

Ensuite, tout en passant l'index à upeao, exécutez la boucle de 0 à la dernière.

Peut-être que j'écrirais for i in range (len (array)). Je n'utilise que n ou ici. Est-ce difficile à lire? ~~ Shiranai ~~

Et une boucle descendante. Honnêtement, la raison pour laquelle j'ai décidé d'écrire cet article. ~~ C'est difficile à comprendre ~~

Au fait, array[0] , array[i] = array[i] , array[0] Est-ce un échange. Il semble que python puisse écrire comme ça, alors je l'ai essayé. Une seule ligne suffit.

Qu'est-ce que monter?

upeap accepte les tableaux et les index comme arguments. Il reçoit array et i du corps. Au fait, «while n» signifie «tandis que n! = 0». Si ce n'est pas 0, c'est vrai.

upheap.py


def upheap(array, n):
    while n:
        parent = int((n - 1) / 2)
        #Essayez de prendre la valeur de parent> enfant
        if array[parent] < array[n]:
            array[n] , array[parent] = array[parent] , array[n]
            n = parent
        else:
            break

C'est la tâche de transmettre un petit nombre à l'enfant. Le tas est fondamentalement une règle selon laquelle "les parents sont petits, les enfants sont grands", donc si vous ne le faites pas une fois, vous ne pourrez pas transmettre un grand nombre aux enfants. Ainsi, une fois que vous passez un grand nombre vers le haut (côté parent), préparez-vous à transmettre un grand nombre à l'enfant.

before [1, 2, 3, 4, 5, 3, 2, 1, 4, 3, 4, 5, 0] upheap [5, 4, 5, 4, 4, 3, 2, 1, 1, 3, 3, 2, 0]

Il sera trié comme ça

Qu'est-ce que Downheep?

downheap prend un tableau et un index comme arguments. Il reçoit le tableau et i-1 du corps.

downheap.py


#racine[0]Le tas(0~n)Déplacer vers la position optimale
def downheap(array, n):
    if n==0: return
    parent = 0
    while True:
        child = 2 * parent + 1 # array[n]Élément enfant de
        #Sortez de l'élément
        if child > n:
            break
        #S'il y a un enfant à côté de vous et à gauche <à droite, regardez l'enfant à droite
        if (child < n) and array[child] < array[child + 1]:
            child += 1
        #Swap si le parent est plus petit que l'enfant
        if array[parent] < array[child]: 
            array[child] , array[parent] = array[parent] , array[child]
            
            parent = child; #Conserve l'index après le remplacement
        else:
            break

J'ai ajouté beaucoup de notes, mais n'est-ce pas encore difficile à comprendre? Comme condition préalable, avant d'entrer dans cette fonction array[0] , array[i] = array[i] , array[0] Faire. (Je suis la partie focalisée) Ce faisant, le nombre le plus élevé est transmis à l'enfant le plus bas avant le tri, et le plus grand nombre à transmettre ensuite est amené au parent le plus élevé. Peut être dit

before[1,2,3,4,5,3,2,1,4,3,4,5,0] upheap[5, 4, 5, 4, 4, 3, 2, 1, 1, 3, 3, 2, 0] [5, 4, 3, 4, 4, 2, 2, 1, 1, 3, 3, 0, 5] [4, 4, 3, 1, 4, 2, 2, 0, 1, 3, 3, 5, 5] [4, 4, 3, 1, 3, 2, 2, 0, 1, 3, 4, 5, 5] [4, 3, 3, 1, 3, 2, 2, 0, 1, 4, 4, 5, 5] [3, 3, 3, 1, 1, 2, 2, 0, 4, 4, 4, 5, 5] [3, 1, 3, 0, 1, 2, 2, 3, 4, 4, 4, 5, 5] [3, 1, 2, 0, 1, 2, 3, 3, 4, 4, 4, 5, 5] [2, 1, 2, 0, 1, 3, 3, 3, 4, 4, 4, 5, 5] [2, 1, 1, 0, 2, 3, 3, 3, 4, 4, 4, 5, 5] [1, 0, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5] [1, 0, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5] [0, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5]

Voyez-vous que lorsque l'indice de mise au point augmente, les nombres triés s'accumulent dans les données inférieures? Cela vous donnera un bon tri.

finalement

Cette fois, j'organisais les algorithmes en écrivant un article, mais j'ai fait beaucoup d'erreurs, j'ai donc tracé et vérifié pour que mon explication soit la plus correcte possible. Ce type de formulaire est une étude, j'espère donc pouvoir continuer avec l'auto-satisfaction.

référence

[Référence: A] https://webbibouroku.com/Blog/Article/py-heapsort ~~ Marupaku ~~ Je l'ai cité. Je pense que le chef de famille donne une explication plus précise, donc si vous n'aimez pas quelque chose qui est mal mâché, veuillez le comprendre au chef de famille.

Recommended Posts

Les débutants en Python organisent des tris de tas
Les débutants en Python organisent des tri rapides
Les débutants en Python organisent des sortes de bulles
Les débutants pratiquent Python
Note du débutant Python
Guide du débutant Python (fonctions)
Python débutant touche Pytorch (3)
Manuel python pour les débutants
Guide du débutant du dictionnaire Python
Python débutant touche Pytorch (1)
Python débutant touche Pytorch (2)
Guide du débutant Python (Introduction)
OpenCV pour les débutants en Python
Organiser les types en Python
Flux d'apprentissage pour les débutants en Python
fonction de mémorandum python pour débutant
Construction de l'environnement Python3 (pour les débutants)
Organiser l'environnement de développement Python
3 raisons pour lesquelles les débutants en programmation devraient commencer avec Python
Python #function 2 pour les super débutants
Guide du débutant Python (Variations / Tableaux)
Grammaire de base Python pour les débutants
Pandas 100 coups pour les débutants en Python
Python #function 1 pour les super débutants
#List Python pour les super débutants
~ Conseils pour les débutants de Python présentés avec amour par Pythonista ③ ~
Python
Python pour les super débutants Super débutants Python # dictionnaire type 1
Résumé de l'apprentissage automatique par les débutants de Python
Python #index pour les super débutants, tranches
Mémo d'automatisation de saisie par Python débutant
<Pour les débutants> bibliothèque python <Pour l'apprentissage automatique>
Fonction Python #len pour les super débutants
Web scraping pour les débutants en Python (1)
# 2 Les débutants en Python défient AtCoder! ABC085C --Otoshidama
Exécutez unittest en Python (pour les débutants)
Mémorandum du débutant Mouvement "isdigit" Python
Web scraping pour les débutants en Python (4) -1
Python #Hello World pour les super débutants
Python pour les super débutants Super débutants Python # dictionnaire type 2
les débutants en python ont essayé de le découvrir
Apprenez les bases de Python ① Débutants élémentaires
[Python] Compte-rendu de la réunion d'étude pour les débutants (7/15)
Réponse à la sélection des débutants d'AtCoder par Python3
[Épisode 2] Les débutants ont essayé Numeron AI avec python
[Épisode 3] Les débutants ont essayé Numeron AI avec python
Mémorandum des débutants en python
Mettons ensemble Python pour les super débutants
[Épisode 0] Un débutant a essayé Numeron AI avec python
[Épisode 1] Un débutant a essayé Numeron AI avec python
10 erreurs Python communes aux débutants
[Python] Lire des images avec OpenCV (pour les débutants)
[Part1] Scraping avec Python → Organisez jusqu'à csv!
Organisez les données séparées par dossier avec Python
Création WebApi avec Python (création CRUD) Pour les débutants
Comment les débutants en Python commencent avec Progete
Ensemble d'entrées standard Atcoder pour les débutants (python)
[Pour les débutants] Essayez le web scraping avec Python
Un manuel pour les débutants réalisé par des débutants Python