Wie begründet man die Anwendung der Sortieralgorithmen auf gegebene Beispiele?
Hallo liebes Forum,
ich versuche mich gerade etwas an dem Thema Sortieralgorithmen.
Die Theorie von Insertion Sort, Quicksort, Mergesort, Heapsort, Selection Sort, Bubblesort ist mir bekannt, habe auch jeden schon mal selbst programmiert und etwas getestet, nur war mir die Anwendung nie richtig klar.
Besser gesagt, wie und wann werden die außerhalb der Theorie verwendet.
Mir ist klar, dass man Insertion Sort und Selection Sort wegen ihrer mäßigen Worst Case Laufzeit nur für geringe Datenmengen einsetzt, bzw Insertion Sort auch, wenn die Daten schon vorher stark sortiert wurden.
Quicksort, Mergesort und Heapsort, weißen für großen Datenmengen die besten Laufzeiten auf, wobei man bei Quicksort darauf achten muss, das die zu sortierenden Elemente nicht schon sortiert sind, denn sonst geht die Laufzeit im Worst Case katastrophal nach oben. Weiter ist wenn es um die Speicherkapazität des Systems geht, Heapsort und vielleicht auch Qicksort zu bevorzugen, denn dank des speicherns der Ergebnisse auf ein Hilfsarray ist Mergesort ziemlich Speicher verbrauchend.
Nun habe ich diese ehemalige Klausuraufgabe aus einer Uni gefunden wobei es natürlich keine richtige Musterlösungen gab, sondern nur ein Hinweis (steht in Klammern), ich aber gerne einmal wüsste, wie man es richtig lösen könnte.
Aufgabe:
"Wählen Sie den effizientesten Algorithmus um diese Probleme zu lösen, begründen Sie außerdem ihre Entscheidung mittels der Kriterien Laufzeit und Stabilität.
Eine kurze Begründung ist ausreichend! "
- An einer Verkehrskreuzung wurde über 10 Tage hinweg die Anzahl der Autos gezählt, die links abbiegen. Die Tageswerte liegen zwischen 10 und 2000 Autos. (SelectionSort)
- An hunderten Wetterstationen Weltweit werden seit 1950 Temperaturwerte gesammelt. Die Werte werden auf ganze Zahlen gerundet. Der niedrigste Wert ist -89°C und der höchste 70°C. Insgesamt sind es ca. 1 Mrd. Werte. (CountSort)
- Im Sonnensystem des Sterns "Sonne" gibt es 8 Planeten. Ihr Abstand zur "Sonne" ist zwischen 58 Mio. Km und 4495 Mio. Km. Die Planeten sollen Danach sortiert werden. (BubbleSort)
- Ein Online-Shop hat ein Bewertungssystem für Seine Produkte, auf der Startseite sollen alle Produkte absteigend nach der Anzahl ihrer Bewertungen angezeigt werden. Diese Anzahl liegt in einem Array von Structs als Wert vor. Die Startseite soll jede Minute aktualisiert werden, somit wird der Algorithmus 1x pro Minute laufen. Da der Shop noch sehr klein ist, kommen selten neue Bewertungen zu Produkten dazu. (InsertionSort)
- Ein neuer Zufallsgenerator hat 1 Mrd. Zahlen mit max. 512 Bit generiert. Um zu prüfen, wie gleichmäßig die Zahlen verteilt sind, sollen sie sortiert werden. (MergeSort)
Über eure Hilfe wäre ich sehr Dankbar
LG
Lara
2 Antworten
Okay, schauen wir doch mal, bei 1 sind es 10 zu sortierende Werte, da möchte man einen Algorithmus, der in-place arbeitet und interativ ist.
Bei 2 möchte man Zahlen sortieren, es sind sehr viele (aber kleine) Zahlen. DCS ist hier linear in der Problemgröße, die Zahlen sind auch zu klein, als daß sich ein Radix-Exchange lohnen könnte.
3 Stell sich IMHO ähnlich wie 1 dar, warum hier BubbleSort ggü. Selectionsort verwendet wurde, keien Ahznung, die Stabilität spielt heir keien Rolle.
Bei 4. Insertion Sort macht genau das, er steckt neue Werte an die richtige Position in den bereits sortierten, d.h. ich muß nicht immer neu sortieren, sondern kann explizit nur die wenigen neu hinzugekommenen an ihre Position stopft. (D.h. Insertion Sort basiert im Endeffekt auf sortiertem Einfügen.
Bei 5: Mergesort ist schnell und kann im Gegensatz zu Quicksort sehr leicht auch mit Bändern oder sonstigen externen Speichern arbeiten.
Sagen wir mal so, wenn du dir die Funktionsweise der Algorithmen anschaust, sind sie alle für einen bestimmen Fall optimiert und zwar, wie die zu sortierenden Informationen vorliegen. Sind es Buchstaben, Zahlen, können sie zunächst gruppiert werden, wie viel Inhalt ist zu sortieren, kann man Parallelitäten nutzen, etc ... Je nach dem ist der eine Algorithmus schneller als der andere, weil er weniger Schritte benötigt
Schau dir mal folgendes Video an: https://youtu.be/kPRA0W1kECg
Hey.
Das Video kenne ich, nur bringt es mir gerade nicht sehr viel :=)
LG
Lara