Comprendre le tri par insertion : une approche basée sur des questions

Dans cet article de blog, nous adopterons une approche basée sur des questions pour comprendre les principes fondamentaux de l'algorithme de tri par insertion. J'ai proposé cette approche alors que j'essayais de trouver une meilleure façon de comprendre l'algorithme d'insertion et d'autres que je découvrirai bientôt. Je voulais construire une stratégie que je pourrais appliquer à la plupart, sinon à la totalité, des algorithmes que j'apprendrai. Pendant que j'y réfléchissais, j'étais sûr que je devrais peut-être utiliser la réflexion sur les premiers principes

Inspirée de la réflexion sur les principes premiers, cette approche consiste d'abord à essayer de comprendre l'algorithme, que notre compréhension initiale soit vague ou claire. Nous identifions ensuite les petits concepts ou mécanismes impliqués qui composent l'algorithme. En formant des questions autour de ces mécaniques ou de ces minuscules concepts. Nous essayons essentiellement de comprendre le fonctionnement de l'algorithme sous différents angles, en nous concentrant sur la résolution des questions que nous nous sommes posées par nous-mêmes.

La réponse que vous formez peut ou non ressembler initialement à la syntaxe utilisée dans l'algorithme réel. L'objectif devrait être de répondre à la question par vous-même, que la syntaxe soit proche ou non. Une fois que vous avez une compréhension claire, vous pouvez ensuite convertir, fusionner votre (vos) réponse(s) pour utiliser une syntaxe similaire à la mise en œuvre réelle de l'algorithme. Je pense que ce processus vous permet d'explorer des formes alternatives de code, de comprendre pourquoi une syntaxe spécifique est utilisée, de mieux gérer les cas extrêmes par vous-même.

Je pense que cette méthode garantit que nous comprenons la théorie et le raisonnement derrière chaque ligne de code, rendant le processus de mise en œuvre plus intuitif et significatif. Les questions suivantes et le processus de réflexion que j'ai suivi m'ont aidé à mieux comprendre le tri par insertion et m'ont permis de le coder efficacement.

Pour vous, les questions pourraient être différentes ; ils pourraient être plus nombreux, moins nombreux ou complètement différents. Certains pourraient dire que cela s'apparente à de l'ingénierie inverse, peu importe comment vous l'appelez, cette méthode m'a permis d'avoir une compréhension approfondie de l'algorithme de tri par insertion. J'espère que cela fera la même chose pour vous pour tout autre algorithme. Alors, allons-y !

Implémentation du tri par insertion

C'est la forme de code que nous finirons par implémenter pour le tri par insertion.

def insertion_sort(values):

    for new_value_index in range(1,len(values)):

        new_value = values[new_value_index]

        index = new_value_index-1
        while index>=0:
            if values[index]<new_value:break
            values[index+1] = values[index]
            index-=1

        values[index+1] = new_value

Questions

Étant donné une liste triée, à l'aide de la boucle while, imprimez les valeurs de droite à gauche.

values = [4,8,12,16,20,24,30]
# given a sorted list, using while loop, print values from right to left.

index = len(values)-1
while index>=0:
    print(values[index],end = " ")
    index-=1

Étant donné une liste triée et une nouvelle valeur, recherchez l'index auquel la nouvelle valeur doit être insérée pour garder la liste triée.

values = [4, 8, 12, 16, 20, 24]
new_value = 14

# using while loop, if traversing from right to left

index = len(values)-1
while index>=0:
    if values[index]<new_value: break
    index-=1

print(values,new_value,index)

Étant donné une liste triée et une nouvelle valeur, insérez la nouvelle valeur dans la liste pour qu'elle reste triée.

values = [4, 8, 12, 16, 20, 24]
new_value = 14

# if traversal from right to left

index = len(values)-1
while index>=0:
    if values[index]<new_value:break
    index-=1

values = values[:index+1] + [new_value] + values[index+1:]
print(values)

Étant donné une liste triée, puis complétée par une nouvelle valeur, déplacez la nouvelle valeur vers la position d'index donnée.

values = [4, 8, 12, 16, 20, 24, 30]

new_value = 14

values.append(new_value)

given_index = 3

# above given

n = len(values)-1

index = n-1
while index>given_index:
    values[index+1] = values[index]
    index-=1

print(values)

values[given_index+1] = new_value

print(values)

Étant donné une liste triée, puis complétée par une nouvelle valeur, triez la liste.

values = [4, 8, 12, 16, 20, 24, 30]

new_value = 14

values.append(new_value)

print(values)

### given a sorted list, then appended with new value, sort the list
####

n = len(values)-1
new_value = values[-1]

# find the index at which the value is to be inserted
# right to left
index = n-1
while index>=0:
    if values[index]<new_value:break
    index-=1
given_index = index 
print("given_index : "  , given_index)

# move the values forward by one step until we reach the given index
index = n-1
while index>given_index:
    values[index+1] = values[index]
    index-=1

values[index+1] = new_value

print(values)

Étant donné une liste triée, puis ajoutée à une ou plusieurs nouvelles valeurs, triez la liste.

values = [4, 8, 12, 16, 20, 24, 30]

new_values = [14,32]

values += new_values

print(values)

# given a sorted list, then appended with two new value(s), sort the list

n = len(values)-1

new_value_start_index = n - 1

print(new_value_start_index, values[new_value_start_index])

for new_value_index in range(new_value_start_index,len(values)):

    new_value = values[new_value_index]

    index = new_value_index-1
    while index>=0:
        if values[index]<new_value: break
        values[index+1] = values[index]
        index-=1

    values[index+1] = new_value

print(values)

Étant donné une liste, triez-la.

import random

values = random.sample(range(10,90), k = 10)

values

print(values)

for new_value_index in range(1,len(values)):
    new_value = values[new_value_index]

    index = new_value_index-1
    while index>=0:
        if values[index]<new_value:break
        values[index+1] = values[index]
        index-=1
    values[index+1] = new_value

print(values)

Implémentation du tri par insertion

def insertion_sort(values):
    for new_value_index in range(1,len(values)):
        new_value = values[new_value_index]

        index = new_value_index-1
        while index>=0:
            if values[index]<new_value:break
            values[index+1] = values[index]
            index-=1
        values[index+1] = new_value

Ressources supplémentaires

Bien que j'aie initialement travaillé sur un ensemble complet de questions pour mieux comprendre l'algorithme, les questions ci-dessus sont, à mon avis, importantes pour mieux comprendre le tri par insertion. Inclure toutes les questions sur lesquelles j'ai travaillé rendrait le message assez long.

Pour ceux qui souhaitent voir toutes les questions, j'ai créé un Jupyter Notebook contenant l'ensemble complet des questions avec mes propres réponses, ce qui m'a permis de comprendre complètement la mise en œuvre du tri par insertion.

Je vous encourage à consulter le cahier si vous souhaitez approfondir vos connaissances.

Les corrections et suggestions sont les bienvenues.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!