Anwendung der Sortieralgorithmen

Zielsetzung

Bei der Entwicklung von Sortieralgorithmen haben wir bisher Zahlen als einfachste sortierbare Daten betrachtet. Bei realen Anwendungen hat man es meist mit komplexeren Datensätzen zu tun, die aus verschiedensten Daten bestehen. So könnte eine Datei mit Adressdaten wie den folgenden gegeben sein, die nach einem bestimmten Kriterium (z.B. dem Nachnamen) sortiert werden soll.

Krause,Stefanie,Brandenburgische Str. 20,74343,Sachsenheim
Brandt,Mandy,Scharnweberstrasse 84,68199,Mannheim Almenhof
Möller,Jens,Schoenebergerstrasse 47,08313,Bernsbach
Herzog,Marco,Scharnweberstrasse 90,61130,Nidderau
Schmitz,Andreas,Meininger Strasse 84,66539,Neunkirchen Ludwigsthal
Ebersbacher,Michelle,Alt-Moabit 10,06691,Zeitz
Koertig,Christine,Hardenbergstraße 82,66887,Niederalben
Schmidt,Vanessa,Paderborner Strasse 44,86359,Gersthofen
Meister,Stephan,Fasanenstrasse 17,22605,Hamburg Othmarschen
Schreiber,Barbara,Stresemannstr. 56,66592,St Wendel
...

Download der gesamten Datei: adressdaten.csv

Ziel ist es, ein gegebenes Sortierprogramm so anzupassen, dass man es zur Sortierung des vorliegenden Datenmaterials benutzen kann.

Ein gegebenes Sortierprogramm

Wir gehen von einem getesteten Programm zum Sortieren von Zahlen aus. Im vorliegenden Fall handelt es sich um eine Implementierung von Quicksort, bei der die Sortierung durch Vertauschungen innerhalb der gegebenen Liste durchgeführt wird.

# Sortieralgorithmus
def quicksort(L, anfang, ende):
    pivot = L[anfang]
    links = anfang
    rechts = ende
    while links <= rechts:
        while L[links] < pivot:
            links = links+1
        while L[rechts] > pivot:
            rechts = rechts-1
        if links <= rechts:
            if links < rechts:
                h = L[links]
                L[links] = L[rechts]
                L[rechts] = h
            links = links+1
            rechts = rechts-1
    if anfang < rechts:
        L = quicksort(L, anfang, rechts)
    if links < ende:
        L = quicksort(L, links, ende)
    return L

# Test
L = [25, 17, 32, 56, 25, 19, 8, 66, 29, 6, 20, 29]
print(L)
L = quicksort(L, 0, len(L)-1)
print(L)

Aufgabe 1

Teste selbst das gegebene Sortierprogramm.

Anpassung des Sortierprogramms

Wir gehen nach wie vor davon aus, dass die Daten in der oben gezeigten Weise in einer Datei vorliegen.

Bevor der gegebene Sortieralgorithmus auf diesen Daten operieren kann, müssen die Daten zunächst in eine Listenform überführt werden.

[
('Krause','Stefanie','Brandenburgische Str. 20','74343,Sachsenheim'),
('Brandt','Mandy','Scharnweberstrasse 84','68199','Mannheim Almenhof'),
('Möller','Jens','Schoenebergerstrasse 47','08313,Bernsbach'),
...
]

Entsprechend sollen die dann sortierten Daten wieder in der oben gezeigten Weise in einer Datei abgespeichert werden.

Diese Datentransformationen können mit Funktionen des Python-Programms listenoperationen_zum_laden_und_speichern.py durchgeführt werden:

Wenn man jetzt das oben gezeigte Sortierprogramm anwenden möchte, muss man zum einen auf die vorgegebenen Funktionen zur Datentransformation zurückgreifen. Zum anderen muss man die Vergleichsoperation zum Vergleich der Datensätze anpassen. Der folgende Quelltext zeigt, wie das geht.

from listenoperationen_zum_laden_und_speichern import *

# Vergleich von Datentupel
def kleiner(d1, d2):
    return d1[0] < d2[0]

# Sortieralgorithmus
def quicksort(L, anfang, ende):
    pivot = L[anfang]
    links = anfang
    rechts = ende
    while links <= rechts:
        while kleiner(L[links], pivot):
            links = links+1
        while kleiner(pivot, L[rechts]):
            rechts = rechts-1
        if links <= rechts:
            if links < rechts:
                h = L[links]
                L[links] = L[rechts]
                L[rechts] = h
            links = links+1
            rechts = rechts-1
    if anfang < rechts:
        L = quicksort(L, anfang, rechts)
    if links < ende:
        L = quicksort(L, links, ende)
    return L

# Test
text = textAusDatei('adressdaten.csv')
listeDaten = tupelListeAusText(text)
listeDatenSortiert = quicksort(listeDaten, 0, len(listeDaten)-1)
textNeu = textAusTupelListe(listeDatenSortiert)
textInDateiSpeichern('adressdaten_sortiert_name.csv', textNeu)

Aufgabe 2

(a) Teste das angepasste Sortierprogramm. Beachte, dass die Dateien listenoperationen_zum_laden_und_speichern.py und adressdaten.csv im selben Verzeichnis wie das Programm vorliegen müssen.

(b) Erläutere die Veränderungen im angepassten Sortierprogramm.

Aufgabe 3

Hier ein Programm zum Sortieralgorithmus Selectionsort. Passe es so an, dass mit dem veränderten Programm die oben gegebenen Adressdaten nach dem Nachnamen / der Postleitzahl sortiert werden.

# Sortieralgorithmus
def selectionsort(L):
    n = len(L)
    i = 0
    while i < n-1:
        minpos = i
        m = i+1
        while m < n:
            if L[m] < L[minpos]:
                minpos = m
            m = m+1
        h = L[i]
        L[i] = L[minpos]
        L[minpos] = h
        i = i+1
    return L
        
# Test
L = [25, 17, 32, 56, 25, 19, 8, 66, 29, 6, 20, 29]
print(L)
L = selectionsort(L)
print(L)

Eventuell muss du etwas Geduld bei der Ausführung des angepassten Programms haben. Hast du auch schon eine Vermutung, warum man das so ist? (Zum Vorabtesten kannst ja kleinere Datenbestände benutzen.)

Aufgabe 4

Mit einem geeigneten Programm sollen die Datensätze der oben gegebenen Adressdaten nach der Postleitzahl sortiert werden. Bei gleicher Postleitzahl soll nach dem Nachnamen (und evtl. auch nach dem Vornamen) sortiert werden.