Einfügungssortierung verstehen: Ein fragengesteuerter Ansatz

In diesem Blogbeitrag verfolgen wir einen fragengesteuerten Ansatz, um die Grundlagen des Einfügungssortierungsalgorithmus zu verstehen. Ich bin auf diesen Ansatz gekommen, als ich versuchte, den Einfügungsalgorithmus und andere, die ich bald kennenlernen werde, besser zu verstehen. Ich wollte eine Strategie entwickeln, die ich auf die meisten, wenn nicht alle Algorithmen, die ich lernen werde, anwenden kann. Während ich darüber nachdachte, war ich mir sicher, dass ich möglicherweise nach den ersten Prinzipien denken muss

Inspiriert durch das Denken nach den ersten Prinzipien, beinhaltet dieser Ansatz zunächst den Versuch, den Algorithmus zu verstehen, unabhängig davon, ob unser anfängliches Verständnis vage oder klar ist. Anschließend identifizieren wir die winzigen Konzepte oder Mechanismen, aus denen der Algorithmus besteht. Indem wir Fragen zu diesen Mechanismen oder winzigen Konzepten stellen. Wir versuchen im Wesentlichen, die Funktionsweise des Algorithmus aus kleinen, unterschiedlichen Perspektiven zu verstehen, wobei wir uns darauf konzentrieren, die Fragen zu lösen, die wir selbst formuliert haben.

Die von Ihnen formulierte Antwort ähnelt möglicherweise zunächst der im tatsächlichen Algorithmus verwendeten Syntax. Das Ziel sollte darin bestehen, die Frage selbst zu beantworten, unabhängig davon, ob die Syntax nah ist oder nicht. Sobald Sie ein klares Verständnis haben, können Sie Ihre Antwort(en) konvertieren und zusammenführen, um eine Syntax zu verwenden, ähnlich der tatsächlichen Implementierung des Algorithmus. Ich glaube, dieser Prozess ermöglicht es Ihnen, alternative Formen von Code zu erkunden, zu verstehen, warum eine bestimmte Syntax verwendet wird, und selbst besser mit Randfällen umzugehen.

Ich glaube, dass diese Methode sicherstellt, dass wir die Theorie und die Argumentation hinter jeder Codezeile verstehen, wodurch der Implementierungsprozess intuitiver und aussagekräftiger wird. Die folgenden Fragen und der Denkprozess, den ich durchlaufen habe, haben mir geholfen, Insertion Sort besser zu verstehen und es mir ermöglicht, es effektiv zu programmieren.

Für Sie könnten die Fragen anders sein; sie könnten mehr, weniger oder ganz anders sein. Manche würden vielleicht sagen, dass dies mit Reverse Engineering vergleichbar ist. Wie auch immer Sie es nennen, diese Methode ermöglichte es mir, ein umfassendes Verständnis des Insertion-Sort-Algorithmus zu erlangen. Ich hoffe, dass es bei jedem anderen Algorithmus dasselbe für Sie bewirkt. Also, lasst uns eintauchen!

Implementierung der Einfügesortierung

Dies ist die Codeform, die wir letztendlich für Insertion Sort implementieren werden.

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

Fragen

Anhand einer sortierten Liste werden die Werte mithilfe der While-Schleife von rechts nach links gedruckt.

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

Suchen Sie anhand einer sortierten Liste und eines neuen Werts den Index, an dem der neue Wert eingefügt werden soll, um die Liste sortiert zu halten.

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)

Fügen Sie bei einer sortierten Liste und einem neuen Wert den neuen Wert in die Liste ein, damit er sortiert bleibt.

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)

Wenn Sie eine sortierte Liste erhalten und dann einen neuen Wert anhängen, verschieben Sie den neuen Wert an die angegebene Indexposition.

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)

Angenommen, Sie haben eine sortierte Liste und dann einen neuen Wert angehängt, sortieren Sie die 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)

Sortieren Sie die Liste anhand einer sortierten Liste, an die dann neue Werte angehängt werden.

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)

Sortieren Sie eine gegebene Liste.

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)

Implementierung der Einfügesortierung

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

Zusätzliche Ressourcen

Während ich zunächst eine Reihe umfassender Fragen durchgearbeitet habe, um den Algorithmus besser zu verstehen, sind die oben genannten Fragen meiner Meinung nach wichtig, um die Einfügungssortierung besser zu verstehen. Das Einbeziehen aller Fragen, an denen ich gearbeitet habe, würde den Beitrag ziemlich lang machen.

Für diejenigen, die alle Fragen sehen möchten, habe ich ein Jupyter-Notizbuch erstellt, das den gesamten Fragensatz mit meinen eigenen Antworten enthält, was es mir ermöglichte, die Implementierung von Insertion Sort vollständig zu verstehen.

Ich empfehle Ihnen, einen Blick auf das Notizbuch zu werfen, wenn Sie tiefer in die Materie eintauchen möchten.

Korrekturen und Vorschläge sind willkommen.

Das obige ist der detaillierte Inhalt vonEinfügungssortierung verstehen: Ein fragengesteuerter Ansatz. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!