Zitat von
helga5:
Soll etwas schneller als shellsort sein, da rekursiv.
Soll das heissen, dass rekursiv schneller als iterativ ist?
Nein. Es kommt hier auf das Verfahren an. Quicksort ist zwar von der Komplexität her genauso wie Shellsort (und auch Mergesort), in der Praxis hat sich aber quicksort bewährt, weil es einfach am kompaktesten ist, also pro Vergleich, Vertauschen etc. am wenigsten Overhead produziert.
Eine iterative Variante von Quicksort, die den rekursiven Aufruf mit einem eigenen Stack simuliert, ist noch marginal schneller (ca. 4%).
Wirklich schnell ist nur die Skip list, die sowohl der LL, als auch dem DA (wie komm ich nur auf VA?) in allen Belangen haushoch überlegen ist.