Quicksort

[philSMA]

Hi zusammen,

Ich suche einen einfachen und leicht verstädnlichen Quicksort

in C. Kann mir da jemand helfen??

:confused:

Danke im Vorraus,

PhilSMA

[robotto7831a]

Schau mal hier.

Frank

[Crow T. Robot]

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

[gugelhupf]

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

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

[nic_power]

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

[Knuddlbaer]

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.

[gugelhupf]

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.

[Ganymed]

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...

[gugelhupf]

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