Hi zusammen,

Ich suche einen einfachen und leicht verstädnlichen Quicksort

in C. Kann mir da jemand helfen??

:confused:

Danke im Vorraus,

PhilSMA

Schau mal hier.

Frank

Kein Problem: Nennt sich qsort() und steht nach Einbinden von stdlib.h zur Verfügung. Oder willst du das unbedingt selber neu programmieren?

Nur mal als kleine Klug*******erei :

Wenn Du vorher weisst dass Du mehr als 400 Elemente sortieren willst, so ist Heap-Sort vorzuziehen.

Original geschrieben von gugelhupf

Nur mal als kleine Klug*******erei :

Wenn Du vorher weisst dass Du mehr als 400 Elemente sortieren willst, so ist Heap-Sort vorzuziehen.

Kannst Du das auch begründen? Warum ist ein Heap-Sort vorzuziehen (und wie ist die Abhängigkeit von der Eingabe)?

Nic

Hallo,

da nicht bekannt ist für was der quicksort gebraucht wird sind Diskusionen um die Effizienz egal. Gefordert wurde ein quicksort nicht mehr nicht weniger.

Original geschrieben von nic_power

Kannst Du das auch begründen? Warum ist ein Heap-Sort vorzuziehen (und wie ist die Abhängigkeit von der Eingabe)?

Nic

Ganz einfach. Weil die Laufzeitfunktion bei Heap-Sort für n>=400 eine bessere asymptotische Annäherung an das Optimum O(n log n) erreicht. Ausserdem garantiert Heap-Sort im worst-case O(n log n), was bei Quicksort bei "krummen" Eingabemengen im worst case O(n²) hat.

Wenn Quellen willst...

Andererseits war ja nach Quicksort gefragt wie das Posting vorher schon richtig bemerkt hat.

Original geschrieben von gugelhupf

Nur mal als kleine Klug*******erei :

Wenn Du vorher weisst dass Du mehr als 400 Elemente sortieren willst, so ist Heap-Sort vorzuziehen.

Was ist ein Heap-Sort? Oder besser wie funktioniert er? Hab ich noch nie gehört...

Wer googelt der findet:

http://www.google.de/search?q=heapsort&ie=ISO-8859-1&hl=de&btnG=Google+Suche&meta=cr%3DcountryDE

http://liebknecht-gymnasium.bei.t-online.de/sort/html-Seiten/Heapsort.html