Arten von Sortierverfahren?

Hallo

Es würde mich interessieren welche Arten es von Sortierverfahren in C gibt.
Also in der Schule wurde uns beigebracht, dass direktes Auswählen ein quadratisches Sortierverfahren ist, da man N² Vergleiche braucht.

Des Weiteren wurde uns gesagt, dass es auch ein logarithmisches Sortierverfahren geben würde. Meinem Skript kann ich jedoch nicht entnehmen welches logarithmisch sein sollte. Außerdem meinten ein paar andere User eines anderen Forums, dass es kein logarithmisches Sortierverfahren geben würde.

In meinem Skript hat nur die Binärsuche in einem sortierten Feld etwas mit logarithmisch zu tun. Aber:

Suche != Sortieren

Oder sehe ich da was falsch?

supertux

Nein, das ist richtig, Suchen != Sortieren.

Rein algorithmis kenne ich keine Verfahren, aber QuickSort liegt in nlog(n). HeapSort gehört auch dazu. Mehr Info hier:

http://ad.informatik.uni-freiburg.de/bibliothek/books/ad-buch/k2/slides/

interpreter

http://www.sortieralgorithmen.de/

Suche != Sortieren

Oder sehe ich da was falsch?

Siehst du richtig.

logarithmische Laufzeit
Eine Laufzeit ist logarithmisch, wenn gilt "T(n) = Θ(log(n))" für eine beliebige Basis.

Assymptodisch gute Sortieralgorithmen [T(n) = Θ(nlogn)..Θ(n²)]
Shearsort, Shellsort, Combsort, Bitonicsort

Assymptodisch optimale Sortieralgorithmen [T(n) = Θ(nlogn)]
Quicksort, Mergesort, Bitonic Mergesort, Heapsort, Avlsort, Bsort

Sind das dann keine logarithmischen Sortierverfahren?

Also im Klartext

[] Es gibt logarithmische Sortierverfahren
[] Es gibt keine logarithmischen Sortierverfahren

supertux

Dein erstes Zitat ist Definition, dein zweites ist Tatsache. Nein, rein algorithmiche Algorithmen gibt es nicht, es gibt nur Algorithmen, die in n*log(n) laufen, und das ist besser als n²