Sortiervergleich

Sortier-Vergleich.py

import time
import random
import sys

def progressbar(it, prefix="", size=60, out=sys.stdout):
    count = len(it)
    def show(j):
        x = int(size*j/count)
        print(f"{prefix}[{u'█'*x}{('.'*(size-x))}] {j}/{count}", end='\r', file=out, flush=True)
    show(0)
    for i, item in enumerate(it):
        yield item
        show(i+1)
    print("\n", flush=True, file=out)


def selectionSort(array):
    # Finde die niedrigste Nummer und wechsele die an der richtige stelle
    # n + (n-1) + (n-2) + ... + 1#
    # n * (n+1) / 2
    # Ω(n²) upperbound
    # Ω(n²) lowerbound

    """
    find i from 0 to n-1
        find smallest number between i and n-1
        swap smallest number with i
    """

    for num in range(len(array)):

        low_n = num

        for i in range(num + 1, len(array)):


            # Gehe alle nummer durch, und speichere den niedrigsten wert
            if array[i] < array[low_n]:
                low_n = i

        # setze die niedrigste Zahl an der richtige stelle
        (array[num], array[low_n]) = (array[low_n], array[num])


def bubbleSort(array):
    # Wechsel Nummer mit Folgenummer, wenn Folgenummer größer ist
    # solange bis alle Nummer sortiert sind
    # Ω(n²) upperbound
    # Ω(n) lowerbound

    """
    repeat n-1 times
        for i from 0 to n-2
            if numbers[i] and numbers[i+1] out of order
                swap them
            if no swaps
                quit
    """

    # Schleife durch die Liste
    for i in range(len(array)):

        # Schleife um 2 auffolgende einträge zu kontrollieren
        # wichtig hierbei ist, - 1 von der ganzen Länge, da sonst ein OutofBounds error passiert
        # i wird abgezogen, da, bei jeder Schleife, die letzte Zahl schon sortiert ist
        for j in range(0, len(array) - i - 1):

            # Vergleiche Eintrag mit seinem nächsten Nachbarn
            if array[j] > array[j + 1]:
                # Tausche die Einträge wenn nicht
                # in der richtigen Reihenfolge
                temp = array[j]
                array[j] = array[j + 1]
                array[j + 1] = temp


def mergeSort(array):
    # Teile Liste in Hälften, mergeSort jede list
    # Vereine die Hälften
    # Wenn nur 1 Nummer, Beenden
    # Ω(n*log n) upperbound / lowerbound

    """
    if only one number
        Quit
    else
        sort left half of numbers
        sort right half of numbers
        merge sorted halves
    """

    if len(array) > 1:

        # r ist die der Mittelpunkt zwischen den Array
        # // gibt immer ganzzahlen aus (Beispiel:  5//2 = 2)   (Integer Division)
        r = len(array)//2
        links = array[:r]
        rechts = array[r:]

        mergeSort(links)
        mergeSort(rechts)

        i = j = k = 0

        # Wenn wir am Ende von entweder links oder rechts sind, wähle den größeren von beiden und
        # setze dies an der richtige Stelle
        while i < len(links) and j < len(rechts):
            if links[i] < rechts[j]:
                array[k] = links[i]
                i += 1
            else:
                array[k] = rechts[j]
                j += 1
            k += 1

        # Wenn wir bei entweder links oder rechts keine Nummer mehr haben, setze die restliche Nummer
        # in der Liste
        while i < len(links):
            array[k] = links[i]
            i += 1
            k += 1

        while j < len(rechts):
            array[k] = rechts[j]
            j += 1
            k += 1


def sorting(arg, numberList):
    start = time.perf_counter_ns()
    print("_"*80)
    print()
    if len(numberList) < 1000:
        for i in progressbar(range(len(numberList)), f"{arg}: ", 40):
            if arg.lower() == "selectionsort":
                selectionSort(numberList)
            elif arg.lower() == "bubblesort":
                bubbleSort(numberList)
            elif arg.lower() == "mergesort":
                mergeSort(numberList)
    else:
        print(f"{arg} - Liste zu lang, keine Progressbar")
        if arg.lower() == "selectionsort":
            selectionSort(numberList)
        elif arg.lower() == "bubblesort":
            bubbleSort(numberList)
        elif arg.lower() == "mergesort":
            mergeSort(numberList)

    stop = time.perf_counter_ns()
    print(f"Zeit benötigt: {stop - start} Nanosekunden // {(stop - start)/1000000} Milisekunden")


def printList(liste):
    # Print jeder eintrag in der Liste, getrennt von ein Leerzeichen
    print("\nSortiert ist die Liste: ")
    for i in range(len(liste)):
        if i > 100:
            print('...', end=" ")
            print(liste[len(liste)-1], end=" ")
            break
        else:
            print(liste[i], end=" ")
    print("\n\n")


if __name__ == '__main__':
    numberList = []
    print(f"Willkommen beim Nummer-Sortier Algorithmus")
    n = input("Bitte geben Sie eine Länge der Nummerliste: ")
    for i in range(int(n)):
        numberList.append(random.randint(0, int(n)))


    sorting("mergeSort", numberList)
    sorting("selectionSort", numberList)
    sorting("bubbleSort", numberList)

    printList(numberList)
    input()