# Algo+DS, Uebung 4, Aufgabe 1
# Sortierzeit

from random import random
from time import process_time
# braucht Python-Version 3
# fuer Python 2: folgende Zeile statt der oberen nehmen
# from time import time
# und unten Aufrufe von process_time() durch time() ersetzen

def bubble_sort(array):
    # Quelle: https://realpython.com/sorting-algorithms-python/
    n = len(array)
    for i in range(n):
        already_sorted = True
        for j in range(n - i - 1):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]
                already_sorted = False
        if already_sorted:
            break
    return array

def messung (n):
    test_array = [random() for _ in range(n)]
    start = process_time()
    sorted_array = bubble_sort (test_array)
    zeit = process_time() - start
    print ("n=%11d: t=%f" % (n,zeit))

for i in range(20):
    messung (1000*(i+1))