Quick Sort

[CyberT]

Pozdrav!
Da li netko možda zna kako napraviti quick sort koji će raditi neovisno da li sortiramo listu implementiranu preko polja ili pokazivača? Ako znate molim vas napišite kod, ali može i barem okvirno da znam kako bi trebao izgledat quick sort.
Puno hvala.

[franzi]

Koji programski jezik?

[hudo]

Unaprijed velika isprika na OT, ali mi se cini zgodnim spomenuti jednu anegdotu sa QuickSortom:
bilo je to jedno zupanijsko natjecanje iz programiranja, tamo negdje 96-97, ne pamtim vise. Zadatak je zahtjevao izvodzenje jako brzog sorting algoritma jer su od te godine uvjeli vremenska ogranicenja. Naravno, svi smo mi tamo na natjecanju znali swap i buble sort, ali malo tko je znao quick ili neki drugi napredni i brzi algoritam. Tako da je vecina izgubila dosta bodova na racun sporosti koda. Ali jedan natjecatelj se mudro sjetio da u helpu od pascala postoji ljepo izlistan cijeli kod od quick sorta. Napravio je copy-paste, i pokupio maximalno bodova iz zadatka!
Siguran sam da se turbo pascal da lako skinuti s neta, a u njemu je cijeli algoritam....

[tsereg]

Tako nešto raditi je valjda jedan od najuzaludnijih zadataka. Ne znam tko zadaje takve zadatke?

Ali, ne može ti se dati taj kod ako ne kažeš programski jezik. A i onda to nije baš posve trivijalno. Teoretski, u C++-u bi napisao algoritam koristeći STL-ove iteratore, čime automatski imaš riješeno sortiranje nad svakim kontejnerom koji podržava takav iterator.

Googleaj za stl quicksort (http://www.google.com/search?hl=en&q=stl+quicksort).

Ovo je jedan od prvih linkova gdje imaju zanimljivu diskusiju iz koje saznaješ:
http://www.thescripts.com/forum/thread135722.html

- STL-ov sort() je quick-sort
- koristi random-access iteratore
- STL-ov sort() je zasebno implementiran za kontejner list (vezanu listu), što uopće nije iznenađujuće i pokazuje neobičnost ovakvih zadataka
- no, ako uspiješ napraviti random-access iterator nad list kontejnerom, sort() će sortirati i to

Alternativno, napravi generički kontejner (čisti apstraktni razred je OK) koji ima random-access pristup [funkciju getAt(i)], onda napiši quick-sort funkciju koja prima generički kontejner i koristi getAt(i) da pristua elementima i sortira. Onda deriviraj dva stvarna kontejnera - listu i vektor - implementiraj ih, i to je to.

Konačno, preradi quick-sort algoritam tako da ne skače NA poziciju i, već da skače ZA i mjesta naprijed ili nazad OD neke upamćene poziciji (ako je moguće quick-sort tako izraziti, treba razmisliti malo). Ovo će možda optimizirati rad s dvostruko vezanom listom, a u radu s nizom ionako nema ulogu.

[CyberT]

Jezik može biti c++ ili c.