C: Alternative zu "qsort" (n. rekursiv)

[Gast]

Hi,

gibt es in der C-stdlib eigentlich eine Sortierfunktion auf einem Array, die nicht rekursiv arbeitet? Oder was würde man machen, wenn man qsort durch etwas nicht-rekursives ersetzen müßte?

danke

[Shink]

AFAIK gibts das in der C-stdlib nicht.
Wenn du furchtbar heiß auf einen nicht-rekursiven Sortieralgorithmus bist kannst du natürlich auch QSort nicht-rekursiv implementieren. Die Ausführung geschieht ohnehin nicht-rekursiv.

[Coda]

Wer sagt dass qsort in der Standardbibliothek überhaupt rekursiv implementiert ist?

[Shink]

Keine Ahnung; ich glaub nicht dass das standardisiert ist ob es rekursiv ist oder nicht. Wenns beim Gast nicht rekursiv implementiert wär hätte er die Frage nicht gestellt (denke ich zumindest).

[Trap]

Oder was würde man machen, wenn man qsort durch etwas nicht-rekursives ersetzen müßte?
Man kann jede Rekursion durch eine Schleife ersetzen, man muss dafür nur selbst einen Stack erzeugen und entsprechend verwalten.

[Superguppy]

Du könntest einen Bubblesort oder Insertionsort verwenden - die laufen meines Wissens iterativ. Allerdings würde ich das nur für sehr kleine Datenmengen empfehlen, da insbesondere Bubblesort extremst lahm ist.

[MadMan2k]

Man kann jede Rekursion durch eine Schleife ersetzen, man muss dafür nur selbst einen Stack erzeugen und entsprechend verwalten.
bei qsort braucht man den aber nicht; man kann qsort iterativ in-place machen.

[rotalever]

Man sollte aber immer berücksichtigen, dass quadratische Laufzeit eintreten kann. In vielen Fällen macht das nichts, aber je nach Anwendungsgebiet könnten Sicherheitslücken etc. entstehen.