Die Webseiten der Fachschaft Informatik am ERG Saalfeld


Insertion-Sort

Insertion-Sort ist "in-place" und die Anzahl der Elemente bleibt erhalten.

Beispiel:

Das unsortierte Feld:   2   5   9   8   1   5   2   4  

Wir suchen in dem Feld das größte Element.

Das größte Element wird aus der aktuellen Liste herausgenommen und als letztes Element in der aktuellen Liste eingefügt.   2   5   8   1   5   2   4   9  


Da das größte Element an der letzten Stelle steht, betrachten wird dieses Element nicht mehr. Die nun betrachtete aktuelle Liste ist um ein Element kleiner.

Das größte Element wird aus der aktuellen Liste herausgenommen und als letztes Element in der aktuellen Liste eingefügt.   2   5   1   5   2   4   8   9  


Die beiden größten Elemente stehen an der richtigen Stelle. Das zu betrachtende Feld = aktuelles Feld wird wieder um ein Element kleiner.

Das größte Element wird aus der aktuellen Liste herausgenommen und als letztes Element in der aktuellen Liste eingefügt.   2   1   5   2   4   5   8   9  

usw.

    2   1   2   4   5   5   8   9  

 

Hier wird nicht verschoben, weil das größte Element an der letzten Stelle im aktuellen Feld steht.   2   1   2   4   5   5   8   9  

 

Hier wird nicht verschoben, weil das größte Element an der letzten Stelle im aktuellen Feld steht.   2   1   2   4   5   5   8   9  

 

    1   2   2   4   5   5   8   9  

fertig

 

Das Programm zum Sortieren mit Insertion-Sort sieht so aus:

Programm

from random import randint

#Wir erstellen/würfeln ein Feld
feld = []
for a in range(100):
    feld.append(randint(200,500))

#Ausgabe des unsortierten Felds
for element in feld:
    print(element,end = ' ')
print('\n')

anzahl = len(feld)
feldende = anzahl

for j in range(anzahl):
    #initialisieren für einen Durchlauf
    maximum = -100
    stelle = -1
    feldende = feldende - 1

    #wir suchen in dem Feld die groesste Zahl
    for i in range(feldende+1):
        if feld[i]>maximum:
            maximum = feld[i]
            stelle = i
    del feld[stelle]

    feld.insert(feldende,maximum)

#Ausgabe des sortierten Felds
for element in feld:
    print(element, end = ' ')

 

Der Aufruf sah bei mir so aus:

 

Aufgaben

  1. Bringen Sie das Programm zum Laufen.
  2. Informieren Sie sich über den Befehl "del".
  3. Ändern Sie das Programm so, dass die Anzahl der Elemente als Parameter übergeben wird.
  4. Ändern Sie das Programm so, dass die gewürfelten Zahlen im Bereich von 300 bis 700 liegen.

 

Weblinks

  1. Wikipedia: Insertionsort

 

zurück


© ERG Saalfeld   -   HD. Kirmse + Dustin Wiese     letztes Update 16.08.2022