[C] quicksort non ricorsivo

[Dark_Tranquillity]

Lo sò forse converrebbe molto di più farlo ricorsivo ma a me è stato chiesto di farlo anche iterativo...
quindi cercherei un programma in C che ordini un'array secondo l'algoritmo iterativo del quicksort....
grazie mille....

[Dark_Tranquillity]

up

[recoil]

potresti simulare le chiamate ricorsive con uno stack oppure applicare l'algoritmo del quicksort senza la funzione cosidetta partition che fa l'ordinamento in loco
in pratica il quicksort ti dice che scegli un elemento, detto perno, quindi individui un elemento di indice i tale che tutti gli elementi prima di i siano minori del perno, in i ci finisca il perno e a destra ci vadano gli elementi maggiori.
puoi utilizzare degli array allocati dinamicamente in cui mettere gli elementi a sinistra e destra e poi fonderli
non so quanto questo sia conveniente però

la cosa più efficente penso che sia quella di utilizzare la funzione partition all'interno di un ciclo in cui vai a scegliere di volta in volta gli estremi dell'array in cui operare

altrimenti, al posto di sentire le mie idiozie, traduci in c questa roba
http://www.mvps.org/vb/hardcore/html/iterativequicksort.htm
che sembra visual basic

[Dark_Tranquillity]

ma lo stack è indispensabile in qualsiasi quicksort iterativo???
se dovessi allocarlo dinamicamente che dimensione dovrei dare allo stack?

[Dark_Tranquillity]

up