Mediansuche in C++
Im neuen Artikel geht es um die Mediansuche in C++. In diesem Beispiel habe ich zwei effiziente Algorithmen implementiert und ein kleines Beispielprogramm geschrieben mit dem man die Laufzeit beider Algorithmen vergleicht.
Mediansuche in C++
Die Mediansuche findet das k-te kleinste Element (k’th smallest/largest element) aus einem ungeordneten Array. Es gibt zahlreiche Algorithmen die so eine Suche schneller durchführen, damit man nicht jedes einzelne Element des Arrays mit jedem anderen vergleichen, beziehungsweise das komplette Array sortieren muss.
Implementierung
Den Source Code findet man wie immer auf meiner GitHub Seite. Dieses Mal handelt es sich um ein Konsolenprogramm mit einer einzigen Quelldatei.
Ich habe zwei unterschiedliche Algorithmen für den Vergleich implementiert:
- Randomized selection
eine genaue Beschreibung findet man auf der verlinkten Seite. Randomized selection wird auch Quickselect genannt und ist eine Optimierung von Quicksort. Es wird zufällig ein Index des Arrays gewählt. Ist das Element größer werden alle kleineren Zahlen, ist er kleiner alle größeren Zahlen sortiert. Durch Aufspaltung des Arrays kann im besten Fall (genau die Mitte) der Aufwand für das Sortieren halbiert werden. Vorteil: sehr schnell, Nachteil: rekursiv - Median nach Wirth
bei diesem Algorithmus wird so lange sortiert, bis man mit Sicherheit das k-te Element feststellen kann. Vorteil: braucht keinen zusätzlichen Speicher und läuft als einzelne Funktion ohne Rekursion, Nachteil: langsamer als Quicksort Ansatz
Die Auswertung zeigt neben dem Speicherverbrauch auch immer die Laufzeit jedes Algorithmus. Welcher Algorithmus besser ist kann man pauschal nicht sagen, da das von den Eingangsparametern Abhängt. Da das initiale Array zufällig erstellt wird ist das mit jedem Aufruf des Programms anders.
Fazit
Es gibt in der Literatur zahlreiche unterschiedliche Algorithmen für die Mediansuche in C++. Jeder davon hat bestimmte Stärken und Schwächen, ist aber immer effizienter, als das vollständige Sortieren des Ausgangsarrays. In meinem Beispiel aus dem Studium habe ich zwei davon implementiert und diese werden anhand der Laufzeit miteinander verglichen.
