Materialien zum Unterricht

Sortierverfahren

BogoSort

Kopiere den Quelltext und lass ihn in Python für den Calliope mini V3 laufen.

Erweitere die Liste um weitere Zahlen und beurteile die Laufzeit in Abhängigkeit der Anzahl der Elemente im Array. (Vorsicht, gehe in 1er-Schritten weiter)

Schreibe auf:

  • Welche Werte liefert die Funktion sortiert(liste) unter welchen Bedingungen zurück? Betrachte es z.B. an einer unsortierten und einer sortierten Liste.
  • Wie oft wird die for-Schleife durchlaufen?
  • Notiere für jeden Schleifendurchlauf ein mögliches Aussehen der Liste.
  • Bewerte diese Sortierverfahren als guten oder schlechten Algorithmus. (Im schlechtesten Fall ist die Laufzeit n*n!)
from calliopemini import *
import random

liste=[2,4,6,1,3]
z=0
def sortiert(liste):
    n=len(liste)
    for i in range(n-1):
        if liste[i]>liste[i+1]:
            return False
    return True

while sortiert(liste)==False:
    n=len(liste)
    z+=1
    for i in range(n):
        j = random.randint(0, i)
        liste[i], liste[j] = liste[j], liste[i]
print(liste)
print(z)