Imam malo pitanjce za kolege programere
Vec dva sata se malo igram sa Quick sortom. Naime pokušavam pomoću njega sortirati dvostruko vezanu listu. I malo sam se zapetljo pa sam poceo Googlati za pomoc i naiso sam na par mjesta na rečenicu:
“Nije moguće sortirati vezanu listu sa Quick sortom”.
Zanima me da li je to istina - i za dvostruko vezani i jednostruko vezanu listu
Trebalo bi biti moguće. Možda je problem u tome što taj algoritam onda nije vremena izvođenja Nlog N nego nešto sporiji (radi toga što je nespretno šetati po listi, i “prespajati” pointere) pa definicijski govorimo o različitim aloritmima jer imaju različita vremena izvođenja.
Točno ovo što je melvy rekao.
Osnovna “naredba” u quick-sort algoritmu je “niz[i]”, gdje algoritam čini način na koji izračunavamo “i” iz koraka u korak. Izračun prosječnog (ili najboljeg ili najlošijeg) broja koraka da se sortira niz od n elemenata se bazira na pretpostavci da se operacija “niz[i]” izvodi u jednom koraku. Dakle, “niz[i]” je tzv. “random access” operacija - operacija pristupa bilo kojem elementu niza se izvodi u jednom koraku.
Vezana lista je upravo sušta suprotnost tome. Minimalno je potrebno |i-j| koraka, gdje je i onaj kamo ideš, a j onaj gdje se nalaziš. Zbog toga za niti jedan algoritam sortiranja nad vezanim listama ne vrijedi njegov izračun kompleksnosti (račun u O-notaciji). Svi algoritmi sortiranja su dani nad nizom (za koji - to je definicija niza - vrijedi upravo gornje o operaciji niz[i]).
Ti, naravno, možeš operaciju niz[i] izvesti i nad vezanom listom i automatski imati implementiran bilo koji algoritam sortiranja.
P.S.
Ako riješavaš stvaran problem, onda možeš generirati niz pokazivača na elemente, pa sortirati taj niz pokazivača (pri čemu operacija usporedbe dohvaća elemente indirektno, a ne direktno). Taj niz ti je kao neki “indeks” nad tablicom u bazi podataka.
Jedna ideja, o kojoj sada razmišljam:
Ako bi ti takav niz bio predugačak, onda možeš koristiti algoritme za sortiranje velikih količina podataka (velikih u smislu “ne stane sve u memoriju odjednom”, ali kod tebe to naprosto znači “ne želim imati tako veliki niz, kada već imam sve u vezanoj listi” - niz ti je neka vrsta “radne memorije”, a vezana lista neka vrsta “slijednog spremnika”, poput hard-diska).
Kod takvih algoritama parcijalno sortiraš - uzmeš neki “run” duljine n elemenatan (n < N, gdje je N broj svih elemenata). Tih “n” elemenata sortiraš. Na taj način razdijeliš cijelu vezanu listu u grupe od po n elemenata i svaku grupu sortiraš za sebe unutar sebe. Efektivno, sada imaš parcijalno sortiranu vezanu listu. Imaš run od n elemenata koji je sortiran, a slijedi ga slijedeći run od n elemenata koji je sortiran, itd. Ali nikakve posebne veze između runova nema, osim da slijede jedan drugoga u vezanoj listi.
Kada su sve grupe (runovi) od n elemenata sortirani, onda ih počneš stapati koristeći merge-sort algoritam. Stapaš dva po dva runa od n elemenata dobijajući runove od 2n elemenata. Onda stapaš dva po dva runa od 2n elemenata u runove od 4*n elementa. I to tako nastavljaš sve dok ne stopiš dva preostala runa od N/2 elementa u cijelu listu od N elemenata. Ova operacija stapanja ne iziskuje nikakvu dodatnu memoriju, a slijedna je u svojoj prirodi.
Ovo ti se možda čini komplicirano ako se prvi puta susrećeš s time, ali razmisli malo - prilično je jednostavno i vrlo korisno jer je to najefikasniji način sortiranja neograničeno velike količine podataka - sortiranja kada svi podaci koji se sortiraju ne stanu odjednom u radnu memoriju, pri čemu “n” (duljina runa) može biti proizvoljno mali, a što je veći to bolje.
Osim toga, mislim da će to fascinirati profesora, a pogotovo ako pokažeš da razumiješ polimorfizam u objektno orjentiranom programiranju. Napraviš da algoritam može sortirati i zapise u datoteci na disku (koji su slijedni jedan iza drugoga, upravo kao i elementi u vezanoj listi, pa se mora moći izvesti). I napraviš da algoritam radi i s vezanom listom i na disku. I imaš biblioteku koja sortira datoteku ili vezanu listu proizvoljne duljine, pri čemu će koristiti predvidljivo mnogo memorije za samo izvođenje sortiranja.
P.S. Posljednja rečenica: Ne “predvidljivo mnogo memorije”, već “proizvoljno malo memorije”.
Hvala decki na odgovoru. I meni je bilo čudno što neki tvrde da je to nemoguće napraviti. Istina treba puno tih kretanja i nije efikasno. Sortiranje koje sam izveo pomocu implementacija polja trebalo par minuta da se sortira na 100 000 elemenata
(dakle ne standardno polje nego pomocu vlastitih implementacija polja)
Rjesio bi ja to na efikasniji nacin da se mene pita ali zadatak striktno nalaze sto i kako treba raditi. Malo sam bio zapeo u quick sortu jel ne smjemo koristiti stanardne nacine vec trebamo sve to raditi pomocu vlastitih implementacija (sto je malo komplicirano ali je zanimljivije i bolji izazov9
Sto se tice zadivljavanja profesora to mi nije cilj buduci da zadatke ne radim za sebe vec jednu curu 
ja sam to vec polozil
Hehe, to je sigurno zadatak iz Struktura na drugoj godini FOI-a. Jer i ja to upravo radim… Naime, treba napraviti quicksort algoritam koji ce sortirati listu (bilo da je implementirana pomocu polja ili pomocu vezanih lista - obje imaju iste predefinirane funkcije za dohvacanje elemenata). Neznam, mozda nekomezvuci jednostavno, ali je jako komplicirano. Bar za mene
Bilo bi lako da je dvostruka vezana lista ali ovako je koma…
Da je iz struktura je. Rijesio sam za polje quick sort, ali nije mi se bas dalo zafrkavati sa pokazivacima buduci da nije za mene pa… mislim tu se ne sortiraju konkretne vrijednosti vec se za svaki element mora dlaziti preko pokazivaca itd… i na kraju bi dobio algoritam kojem treba 10 minuta da sortira 10 elemenata…
Moja preporuka kao osoba koja ima 4 iz struktura 
je da ne gubis previse vremena na ovom zadatku. Poslje ce doci pravi konkretni zadaci (mozda nisu laki ali bolje nego ovo apstraktno). Ovaj podzadatak prosle godine nitko nije rijesio
kad vec pominjete povezane liste,da li biste mogli preporuciti neku knjigu ili tuorijal gdje ima sve o listama
hvala