[PYTHON] 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 **.

• Cartes déjà triées dans votre main
• La carte que vous êtes sur le point d'ajouter à partir du tableau --Cartes toujours sur la table

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

• La partie du tableau qui a déjà été triée par ordre croissant
• L'élément que vous regardez dans le tableau
• La partie du tableau qui n'a pas encore été triée par ordre croissant

Par exemple

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.

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. ..