3. Array nach Häufigkeit sortieren

Array nach Häufigkeit sortieren

  • V

    Nexus schrieb:

    VuuRWerK schrieb:

    Ich hoffe Du hast folgendes gelesen:

    Aber Vorsicht, sehr quick and dirty!!!

    Eigentlich wollte ich noch dazuschreiben das ich es so nie machen würde aber das fand ich überflüssig weil es selbstverständlich ist, es ging mir nur darum ein kurzes Beispiel zu liefern wie man es mit priority_queue machen kann, fertig. Zudem wollte ich nicht mehr als 3 minuten investieren.

    Ja, das habe ich in der Tat gelesen. Vielleicht wäre es sinnvoller gewesen, kein Codebeispiel zu liefern. Das ist jetzt nicht böse gemeint, aber als Anfänger nimmt man sich viel zu schnell ein Beispiel an deinem Code. Zumal die Einstellung "Hauptsache, es geht, Code ist ja egal" unter Anfängern sehr verbreitet ist.

    Aber abgesehen davon: Selbst in den drei Minuten wäre es nicht nur möglich gewesen, sondern auch einfacher und kürzer gegangen, ein String-Objekt anstelle eines Zeigers zu nehmen.

    Stimm ich Dir auch voll und ganz zu, aber ich war nicht davon ausgegangen das er völliger Anfänger ist.
    Hab es oben aber mal editiert damit wenigstens der Speicher frei gegeben wird wie es sich natürlich auch gehört!

    Nexus schrieb:

    VuuRWerK schrieb:

    Aber ich muss mich eigentlich nicht rechtfertigen ...

    Nicht? Warum tust du es dann? :p

    Da ich weiß das ich es besser kann und mich ein wenig angekratzt gefühlt habe 🙂

    Gut Schuß
    VuuRWerK 😉

    0
  • Administrator

    knivil schrieb:

    Ich frage mich nur: Warum make_heap, sort_heap, wenn es ein einfaches sort auch tut?

    Weil bei std::sort nicht definiert ist, was für ein Sortieralgorithmus verwendet wird. Es wäre korrekt, wenn ein Bubblesort im Hintergrund verwendet wird. Ich glaube allerdings, dass meistens ein Quicksort verwendet wird. Der kann aber im Worstcase Szenario auf O(n^2) gehen, ist aber eher unwahrscheinlich. Ein Heapsort dagegen hat eine sichere Laufzeit von O(n*log(n)). Der Heapsort ist eines der schnellsten instabilen Sortierverfahen. Informationen dazu:
    http://de.wikipedia.org/wiki/Sortieralgorithmen

    rommi schrieb:

    @Daravere:
    Kann jedem mal passieren dass einem soein Ding rausflutschschschscht.
    Gaaaanz ehrlich ich hab mir deinen Code garnicht angeschaut. Ich weiss praktisch garnix davon... Trotdem lieb von dir!

    Grad garnix? Hmmm, ok.
    Dann vielleicht doch ein paar Hilfestellungen, mal schauen:
    1. Statt getline könntest du gleich die Zahlen über den operator >> einlesen. Leerzeichen werden automatisch ignoriert.
    2. Was ich gemacht habe, ist eine Struktur zu erstellen, welche eine eigene Überladung für den operator >> auf einen std::istream (Basisklasse von std::ifstream ) hat. Die Struktur speichert immer 3 Zahlen und die Häufigkeit.
    3. Ich lese nun immer solche Strukturen als ganzes ein und speichere sie in einem std::vector ab.
    4. Die Struktur hat einen operator < , welcher die Häufigkeit vergleicht. Dadurch ist es mir möglich herauszufinden, welche Häufigkeit mit welchen Zahlen zuerst kommen soll.
    5. Die Sortierung lagere ich allerdings an Standardfunktionen aus. std::make_heap bereitet die Sortierung vor und std::sort_heap führt die Sortierung schlussendlich durch.
    6. Schlussendlich habe ich für die Struktur noch den operator << überladen auf einen std::ostream (Basisklasse von std::ofstream ). Bei der Ausgabe, werden nur die Zahlen ausgegeben und jeweils durch ein Linefeed (neue Zeile) getrennt. Ich gebe also einfach alle Strukturen in meinem std::vector an den Stream.

    Das ganze habe ich "vereinfacht" mit Funktionen und Strukturen aus der Standardbibliothek, wie std::copy , std::ostream_iterator oder std::istream_iterator .

    Aber vielleicht bringt dich dies nun auf die Idee, welche ich genutzt habe.

    Grüssli

    0
  • K

    std::sort nicht definiert ist, was für ein Sortieralgorithmus verwendet wird

    Keine Ahnung was der Standard sagt, aber auf der Seite von SGI steht O( n log n ) als worst case. Ja, der Sortieralgorithmus ist nicht angegeben.

    0
  • V

    Dravere schrieb:

    Der Heapsort ist eines der schnellsten instabilen Sortierverfahen.

    lies auch http://de.wikipedia.org/wiki/Introsort

    0
  • Administrator

    knivil schrieb:

    Keine Ahnung was der Standard sagt, aber auf der Seite von SGI steht O( n log n ) als worst case. Ja, der Sortieralgorithmus ist nicht angegeben.

    Der Standard sagt, dass es ca. O(n * log(n)) sein muss. Aber eben nur ca., vorgeschrieben ist es nicht.

    @volkard,
    Ja, ist mir bekannt. Heapsort bleibt aber einer der schnellsten. Ich sagte ja nicht der schnellste. Introsort wird übrigens auch auf Wikipedia im Artikel von Quicksort erwähnt.
    Danke trotzdem für den Link.

    Grüssli

    0
Anmelden zum Antworten