Besprechung des Quicksort- Codes + weiteres Vorgehen

Zu beginn der Stunde haben wir den Code für das Quicksort-Verfahren besprochen und die Laufzeittests durchgeführt. Hier ein Beispiel-Code:

from random import *
from time import *
def quicksort(L):
    liste = L
    if len(liste) > 1:
        p = liste[0]
        K = []
        G = []
        for element in liste[1:]:
            if element < p:
                K = K + [element]
            else:
                G = G + [element]
        KSortiert = quicksort(K)
        GSortiert = quicksort(G)
        LSortiert = KSortiert + [p] + GSortiert

    else:
        LSortiert = liste
    return LSortiert

nummern = [randint(0,10000) for i in range(32000)]
anfang = time()
quicksort(nummern)
ende = time()
print(ende - anfang)

Weiteres Vorgehen und Kosten-Maß:

Bei den Laufzeittests ist aufgefallen, dass es sich zunächst um eine lineare Abhängigkeit handelte, jedoch bei genauerer Betrachtung auffiel, dass es sich um keine Abhängigkeit handelt und wir nun die Schritte der einzelnen Verfahren des Programmes zählen müssen (hier: wie oft ein Objekt mit einem anderen vergliche wird). Dadurch wird die Messung der Zeit nicht durch Hintergrundprozesse etc. beeinflusst. Diese Zählung nennt man „Kosten-Maß“.

HA: Aufgabe 1 auf dem Inf-Schle Kapitel zur Kostenanalyse:
https://www.inf-schule.de/grenzen/komplexitaet/sortieren/aufwandsanalyse/kostenanalyse

Schreibe einen Kommentar