Insertion Sort
Der Insertion-Sort-Algorithmus ähnelt sehr dem Selection-Sort-Verfahren. Er ist intuitiv aufgebaut, hält den linken Teil des Arrays stets sortiert und iteriert dann Element für Element bis zum Ende des Arrays.
Genauer gesagt beginnt Insertion Sort beim ganz linken Element und bewegt sich schrittweise nach rechts. Sobald wir ein Element finden, das kleiner als die bereits verarbeiteten Elemente zu seiner Linken ist, werden diese nach rechts verschoben, um Platz für das aktuelle Element zu schaffen, das anschließend an seine korrekte Position gesetzt wird. Nehmen wir zum Beispiel das Array
[0, 2, 4, 1, 10, 8] und betrachten das Element 1. Zuerst verschieben wir 4, dann 2 nach rechts und platzieren 1 zwischen 0 und 2. Dadurch erhalten wir [0, 1, 2, 4, 10, 8]. Als Nächstes betrachten wir 10. Weil es größer als alle Elemente zu seiner Linken ist, erfolgt keine Aktion. Dann betrachten wir 8 und verschieben 10 nach rechts, damit 8 zwischen 4 und 10 einsortiert werden kann.a = [...]
for i in range(1, len(a)): # Beginne beim zweiten Element
while i > 0 and a[i] < a[i - 1]: # solange das aktuelle Element kleiner ist
a[i - 1], a[i] = a[i], a[i - 1] # tausche das aktuelle Element mit dem Vorgänger
i -= 1 # behalte den Index des aktuellen Elements im Blick
print(a)Der Insertion-Sort-Algorithmus setzt also das aktuelle Element an der richtigen Stelle im bereits verarbeiteten Teil des Arrays ein. Im schlimmsten Fall – wenn die Elemente des Arrays in absteigender Reihenfolge angeordnet sind – müssen sämtliche Vorgänger eines Elements verschoben werden, um es richtig einzufügen. Diese Situation führt zu insgesamt Operationen.
Lassen Sie uns den Algorithmus an einigen Arrays durchspielen:
[4, 1, -1, 0, 2, 8]
i = 1⇒ tauschen ⇒[1, 4, -1, 0, 2, 8]
i = 2⇒ tauschen ⇒[1, -1, 4, 0, 2, 8]⇒ tauschen ⇒[-1, 1, 4, 0, 2, 8]
i = 3⇒ nichts tun
i = 4⇒ tauschen ⇒[-1, 1, 0, 4, 2, 8]⇒ tauschen ⇒[-1, 0, 1, 2, 4, 8]
i = 5⇒ nichts tun
- print
[-1, 0, 1, 2, 4, 8]
[10, 5, 1, -7]
i = 1⇒ tauschen ⇒[5, 10, 1, -7]
i = 2⇒ tauschen ⇒[5, 1, 10, -7]⇒ tauschen ⇒[1, 5, 10, -7]
i = 3⇒ tauschen ⇒[1, 5, -7, 10]⇒ tauschen ⇒[1, -7, 5, 10]⇒ tauschen ⇒[-7, 1, 5, 10]
[1, 2, 3, 4, 5]
i = 1⇒ nichts tun
i = 2⇒ nichts tun
i = 3⇒ nichts tun
i = 4⇒ nichts tun
Challenge
Gegeben
n ganze Zahlen, sortieren Sie sie mithilfe von Insertion Sort in aufsteigender Reihenfolge.Eingabe
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl
n (1 ≤ n ≤ 1000), die die Anzahl der Elemente im Array angibt.Die nächste Zeile enthält
n durch Leerzeichen getrennte ganze Zahlen ( ≤ ≤ ).Ausgabe
Das Programm soll das Array aus der Eingabe in aufsteigender Reihenfolge ausgeben.
Beispiele
Eingabe | Ausgabe |
5
5 5 3 2 3 | 2 3 3 5 5 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB