Informatik in-a2 2014
Sortierung von Listen mit Mergesort
Hier wird das Mergesort-Verfahren zur Sortierfunktion von Liste als Funktionsaufruf
demonstriert. Dazu wird zuerst eine Liste von 10000 Zufallszahlen erzeugt, die anschließend
sortiert wird. Die Funktion mergesort ruft sich dabei immer wieder selbst auf, bis die zerlegten
Listen eine Länge von 1 besitzen. Dieser Vorgang, bei dem eine Funktion sich selbst
aufruft wird Rekursion genannt. Mit Hilfe der Funktion merge werden dann die zerlegten Listen
in eine neue Liste einsortiert.
Außerdem wird die Rechenzeit berechnet.
Neu war hier:
1. Der Import von Modulen in Python,
2. Zufallszahlen erzeugen,
3. Ausgabe einer Teilliste (linke und rechte Liste),
4. Löschen eines Elements einer Liste,
5. rekursiver Funktionsaufruf (Funktion ruft sich selbst auf).
Beispielcode:
#! /usr/bin/python
###28.4.2014
###Mergesort in Python
import random #Zufallszahlen-Modul importieren
import time # Zeit-Modul importieren
def mergesort(liste):
if len(liste) <= 1: # Wenn die Listelaenge kleiner gleich 1 ist
return liste # gib die Liste zurueck
else:
lListe = liste[:len(liste)/2] #halbe Liste links
rListe = liste[len(liste)/2:] # halbe Liste rechts
#rekursiver Funktionsaufruf
return merge(mergesort(lListe), mergesort(rListe))
def merge(lListe, rListe): #Sortierfunktion
AusgabeListe = []
while lListe != [] and rListe != []:
# Vergleich der linken und der rechten Liste
if lListe[0] <= rListe[0]:
#Kopie des Elements in die Ausgabeliste
AusgabeListe.append(lListe[0])
del lListe[0] # Loeschen des Elements in der Ursprungsliste
else:
#Kopie des Elements der anderen Liste in die Ausgabeliste
AusgabeListe.append(rListe[0])
del rListe[0] # Loeschen des Elements in der Ursprungsliste
# das verbliebene Element der linken Liste in Ausgabeliste schreiben
while lListe != []:
AusgabeListe.append(lListe[0])
del lListe[0] # Loeschen des Elements in der Ursprungsliste
# das verbliebene Element der linken Liste in Ausgabeliste schreiben
while rListe != []:
AusgabeListe.append(rListe[0])
del rListe[0] # Loeschen des Elements in der Ursprungsliste
return AusgabeListe # Rueckgabe der Ausgabeliste
def unsortiert():
liste = [] # Initialisierung einer leeren Liste
# unsortierte Liste mit 10000 Elementen schreiben
for zufallzahl in range(10000):
#Erzeugung einer Zufallszahl aus dem Bereich von 1 bis 10000
zufallszahl = random.randint(1,10000)
liste.append(zufallszahl) #Eintrag der Zufallszahl in die Liste
return liste
###Hauptprogramm
liste = unsortiert() # unsortierte Liste erzeugen
t1 = time.time() # Startzeit ermitteln
ausgabe = mergesort(liste) # Funktionsaufruf
t2 = time.time() # Endzeit ermitteln
print(ausgabe) # Ausgabe des Ergebnisses
print "Dauer: ", t2-t1 # Ausgabe der Rechenzeit
Erstellt am 28.4.2014