Zum Hauptinhalt springen

Zeitmessung

Zeitmessung in Python​

from timeit import timeit
from random import shuffle
from copy import deepcopy

def bogo_sort(a):
while True:
shuffle(a)
is_sorted = True
for i in range(len(a)-1):
if a[i] > a[i+1]:
is_sorted = False
break
if is_sorted:
return a

to_sort = list(range(6))
shuffle(to_sort)

execution_time = timeit(lambda: bogo_sort(deepcopy(to_sort)), number=100)
print('Zeit fĂĽr 100x Sortieren:', execution_time)
Aufgabe

Dateinamen

EF-Informatik/docs/Algorithmen/selection_sort.py

EF-Informatik/docs/Algorithmen/insertion_sort.py

EF-Informatik/docs/Algorithmen/merge_sort.py

EF-Informatik/docs/Algorithmen/zeitmessung.md

FĂĽhren Sie Zeitmessungen fĂĽr die drei Algorithmen durch, indem Sie die Funktion timeit verwenden.

Verwenden Sie fĂĽr n die Werte 100, 1000, 10000, 15000, 20000. (Ab 10000 mĂĽssen Sie die Anzahl der Wiederholungen auf 5 oder tiefer reduzieren.)

Stellen Sie die Messergebnisse tabellarisch und graphisch dar, so dass ein Trend sichtbar wird.

danger

Damit bei der Mehrfachwiederholung stets dieselbe Eingabe verwendet wird, muss die übergebene Liste mit deepcopy aus dem Modul copy kopiert werden. Wenn Sie die Liste nicht kopieren, dann wird die Liste beim Sortieren verändert und die Zeitmessung ist nicht mehr aussagekräftig.

Halten Sie Ihre Messergebnisse im EF Repository unter docs/Algorithmen/zeitmessung.md fest.

def selection_sort(a):
for j in range(len(a) - 1):
key = a[j]
index = j
for i in range(j + 1, len(a)):
if a[i] < a[index]:
index = i
a[j] = a[index]
a[index] = key
return a

to_sort = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
print('Unsortiert:', to_sort)
print('Sortiert: ', selection_sort(to_sort))