Insérer un tri

À partir d'aujourd'hui [INTRODUCTION AUX ALGORITHMES](https://www.amazon.co.jp/Introduction-Algorithms-Thomas-H-Cormen/dp/8120340078/ref=sr_1_2?__mk_ja_JP=Katakana & keywords = introduction + to + algorithm & qid = 1581077652 & sr8 Depuis que j'ai commencé à lire -2), il existe de nombreux contenus simples, mais je vais résumer l'algorithme.

Insérer un tri

Le tri d'un tableau avec 10 éléments par tri par insertion est similaire à l'exemple suivant.

Il y a 10 cartes à jouer sur la table et le nombre de cartes dans votre main est de 0 au début. Je pioche les cartes de la table une par une et les ajoute à ma main, mais je garde toujours ma main triée par ordre croissant. Vous voulez garder votre main bien rangée, comme une carte avec un petit nombre à gauche et une carte avec un grand nombre à droite. Le but de ce processus est que ** les cartes peuvent être classées en trois types **.

Le tri par insertion y prête également attention.

Par exemple

indice 0 1 2 3 4 5 6 7 8 9
valeur 5 3 8 1 2 4 7 6 9 0

Supposons que vous ayez un tableau avec 10 éléments. Pensez-y comme si toutes les cartes étaient encore sur la table. Supposons que vous tiriez une carte à la fois et que vous ne tiriez que la cinquième. Cela équivaut au fait que le tableau a été trié jusqu'à l'index 0-3 et se concentre maintenant sur l'index 4-2.

indice 0 1 2 3 4 5 6 7 8 9
valeur 1 3 5 8 2 4 7 6 9 0

Maintenant, trouvons la position pour insérer ce 2.

――Comparer 2 et 8, 8 est plus grand, remplacez donc les positions de 2 et 8. ――Comparer 2 et 5, 5 est plus grand, alors échangez les positions de 2 et 5. ――Comparer 2 et 3, 3 est plus grand, remplacez donc les positions de 2 et 3. ――Comparer 2 et 1, 2 est plus grand, donc ça se termine ici.

Faites de même pour les 6e à 10e cartes pour obtenir un tableau trié. C'est la procédure de tri des insertions.

def insertion_sort(a) -> None:
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while key < a[j] and j >= 0:
            a[j+1] = a[j] 
            j -= 1
        a[j+1] = key

a = [1, 3, 5, 8, 2, 4, 7, 6, 9, 0]
insertion_sort(a)
print(a)

production

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Le texte que j'ai présenté au début explique diverses choses sur un algorithme, par exemple pourquoi vous pouvez tant diviser les pages avec le tri par insertion, donc j'écrirai un autre article s'il y a quelque chose à lire et à compléter. ..

Recommended Posts

Insérer un tri
Insérer l'implémentation du tri
visualiser le tri par insertion
Trier
Insérer une sorte d'exercices AOJ
SélectionSort
[Python] Trier
Tri naturel
Python #sort
Tri à bulles
Tri à bulles
Fusionner le tri expliqué
Tri pratique du sommeil
Trier par pandas
Tri par bulles, tri par sélection, tri par insertion, tri par shell, tri par fusion, tri rapide, tri par comptage (Python)