Rekurzívne zoradenie prvkov pola – Pascal – Fórum – Programujte.com

Tak neviem ci uz niekto toto robil, ale potreboval by som pomoct. Problem je jednoduchy, vytvorit proceduru ktora zoradi prvky pola, ale rekurziou. Niekde sa tomu asi hovori quicksort. Program mi hlasi chybu 201, zdrojovy subor zdr.in obsahuje pocet prvkov pola a hodnoty .. Tu je moj kod:


program quicksorting;
uses crt;
const max=100;
type ArrInt1=array[1..max] of integer;
var F:text;
B:ArrInt1;
v,i,m:integer;

procedure qsort(var A:ArrInt1; n:integer);
var j,help,m:integer;
begin

for j:=m to (n div 2) do { prva polovica n }
if A[j]>A[n div 2] then
begin
help:=A[j];
A[j]:=A[n div 2];
A[n div 2]:=help;
end;

for j:=n downto (n div 2)+1 do { druha polovica n }
if A[j]<A[n div 2] then
begin
help:=A[j];
A[j]:=A[n div 2];
A[n div 2]:=help;
end;

m:=1;
if n>1 then qsort(A,n div 2);
m:=(n div 2);
if n>1 then qsort(A,n);
end;

begin
m:=1;
clrscr;
assign(F,'zdr.in'); reset(F);
read(F,v);
for i:=1 to v do read(F,B[i]);
for i:=1 to v do write(B[i],' ');
readln;
qsort(B,v);
for i:=1 to v do write(B[i],' ');
readln;
end.

Ked stepujem program tak chyba je hlasena spolu s oznacenim riadka s podmienkou "if A[i]>A[n div 2] then" co je asi 14ty riadok programu.

ja se obavam ze s timdle typem pole budes muset predavat, krom velikosti (resp indexu posledniho prvku) i od ktereho prvku chces to pole projet.... delici prvek se nesrovnava v obou polovinach...

jak vlastne byl ten algoritmus... najdu v jedne polovine prvek ktery tam nepatri ... pak v druhe najdu take nejaky ktery tam nepatri
a vymenim je... stred se mimochodem muze posunout kdyz napriklad prostredni prvek je zrovna nejmensi cislo, tak se vse prohaze do jedny pulky a zustane treba jen ten stred...
(prostredni cislo z pole se bere jako "naivni odhad" prumerneho cisla v poli...)

To KIIV : jaj uz som pochopil co si tym myslel.. musel som to precitat asi 15 krat co ti nesedi.. no vies pre tie dve polovice som tam dal prave tu premennu m, ktora by mala znamenat ten zaciatok, a vzdy ked bude vykonavat vnorenu proceduru qsort tak este pred tym som tam dal zmenit m ked si si vsimol, pre prvu polovicu na 1 a pre tu zvysnu na danej urovni qsort procedury tam je vsunuty ten "m:=n div 2" a qsort na urcitej urovni by to mal uz vybavit od m do polky a od n do polky

co ma vsak teraz napada ked to tak pisem ze asi by trebalo ten druhy for zmenit ... "for j:=n downto (n div 2)+1" na nieco ako "for j:=n downto ((n-m) div 2)"

co sa tyka tej teorie.. mne to profesor(som na gympli) vysvetloval ze to ma byt asi tak: rozdelit pole na polovicu (n div 2) a overovat cleny prvej polovice po n div 2, potom od n div 2 po n (ja to mam naopak, downto..to je jedno) a pri preverovani - z lavej strany prehodit akekolvek cislo ktore je vacsie ako prostredny clen s tymto clenom - a z pravej strany prehodit akekolvek cislo ktore je mensie ako prostredny clen s tymto clenom.. a toto robit aj tychto polovickach pokym sa da, teda pokym ta polovicka neje jedno cislo (preto tam je if n>2 )

myslim ze je prave rychlejsi a efektivnejsi najit v obou prvni co tam nepatri a prohodit je mezi sebou... a takhle pokracovat dokud se "indexy" nestretnou (nebo mozna bylo dokud se nepresahnou... zaroven pak muzes predat ty indexy dal tem rekurzim... tak aby se neprekryvaly samozrejme

To evandar : Ten profesor ti to řekl špatně, takhle to dělat rozhodně nejde. Quicksort pracuje tak, že si vybere pivota, a rozdělí pole na dvě poloviny - s prvky menší, než pivot a s prvky většími, než pivot a zavolá se rekurzivně na obě poloviny, pokud jsou větší než 1. Prakticky se ti stane jen vzácně, že se ti to rozdělí na dvě STEJNĚ velké poloviny.

To evandar : Něco pro inspiraci: http://mircosoft.ic.cz/download/kviksort.zip. Když si ten program spustíš, uvidíš krok po kroku, jak algoritmus pracuje (a je tam i zdroják).

To KIIV : neviem ci by to bolo spravne VYMIENAT indexy, co ak na lavej strane je tych na prehodenie viacej ako tych na prehodenie na pravej strane? to asi bude treba po jednom tie cleny DOSTAT ZA ten deliaci prvok.. poskusam/uvidim/dam vediet :)

To Osiris : Jasne ani ja s tym postupom co som napisal uz nesuhlasim, ked som to pisal a rozmyslal tak som zacal chapat ze som si to z hodiny zapamatal zle.. tym sposobom by som napriklad cislo na pravej strane asi ani nedostal ZA to deliace cislo, len by som tie cleny ktore sa maju hybat prehadzoval s prostrednym a nic z toho..

To Mircosoft : dik za link ale ani ho nepozeram, radsej problemy riesim sam, keby som pozrel ako sa to robi uz by ma to nebavilo, nemal by som nad cim rozmyslat :)

To evandar : delici prvek je jak uz tu zminili Pivot... nehledas prostredni hodnotu.. to by bylo zbytecny zdrzovani... proste vemes prvek kterej je nekde ve stredu pole a prohlasis ho za priblizne stredni hodnotu..
prohozeni bylo mysleno abys pak nedelal razeni: <1; 20> a druha pulka <19; 40> treba

To KIIV : Dobre, vezmem strednu hodnotu, akoze n div 2, jasne, ze ju nehladam.. ja ale vidim problem v tom ze ked vyhladam prvok ktory je treba prehodit, a potom ako ty vravis k nemu najdem v druhej polovici prvok ktory by tiez trebalo prehodit tak to urobim.. ale co ak sa stane ze tych na prehodenie nalavo je viac ako tych na prehodenie napravo.. alebo este horsie, ked na lavo som vsetko co bolo treba prehodit prehodil a na pravo zostali neprehodene veci.. kludne sa moze stat, ze sa nenajde par ktory by sa mohol vymenit.. to sa povie.. "pomocou pivota rozdelit pole na dve pravdepodobne rozne polovice", ale to neje take lahke aspon z mojho pohladu.

Co som to skusal tak som zistoval ake nedostatky na ta moja procedura a cim viac som ju chapal tym som si uvedomoval kolko vela chyb to ma :) napriklad ja som to chcel tak, ze
- prehladavam pole a overujem ci prvok treba prehodit
- ak treba tak ho dam presne ZA ten pomyselny deliaci prvok, ci uz z lava alebo zprava, co je asi zahrnute v tejto nedomyslenej procedure:

procedure qsort(var A:ArrInt1; n:integer);
var j,k,mid,help:integer;

begin
mid:=(n+beg) div 2; { beginning (beg) je na zaciatku 1, v hlavnom programe }
for j:=beg to n do begin { prejdi usek beg - n, stred je mid}
if (A[j]>A[mid]) and (j<mid) then { ak treba prehodit napravo, potom }
begin
help:=A[j]; { uloz si prehadzovany clen }
for k:=j to (mid-1) do A[k]:=A[k+1]; { vsetko po stred presun, vratane pivota }
A[mid]:=help; { na byvale miesto pivota daj posuvane cislo }
mid:=mid-1; { posun index pivota dolava }
end;
if (A[j]<A[mid]) and (j>mid) then { ak treba prehodit nalavo }
begin
help:=A[j]; { uloz si prehadzovany clen}
for k:=j downto (mid+1) do A[k]:=A[k-1]; { vsetko po stred presun }
A[mid]:=help; { na byvale miesto pivota daj posuvane cislo}
mid:=mid+1; { posun index pivota doprava }
end;
end;
{ beg:=1; if n>1 then qsort(A,mid);
beg:=mid; if n>1 then qsort(A,n); }
end;

Cele je to blbost lebo sa tam deje chyba kvoli tomu presunu tych prvkov (k:=...) aha, vid toto
PRIKLAD: ak by som mal taketo konkretne hodnoty 9,8,7,6,5,4,3,2,1,0 (10 hodnot) prehodit podla tej procedury, vysledok by mal byt taky ze 9,8,7,6 sa dostanu napravo od 5ky=deliaci prvok, teda 5,6,7,8,9,4,3,2,1,0... a 4,3,2,1,0 nasledne na lavu stranu, teda 4,3,2,1,0,5,6,7,8,9... to by asi malo urobit po prvom vykonani procedury.. lenze som si neuvedomil ze uz po prvom presune 9ky do tvaru 8,7,6,5,9,4,3,2,1 sa stane to ze procedura chyti druhy prvok a co uz neje ta 8icka ako by som chcel ale 7cka.. na 8micku sa zabudne

heh skusal som v tom cykle davat taku fintu ze ten vodiaci prvok cyklu nech znizi v takom pripade , ze j:=j-1tym padom by sa vratilo k osmicke :D ale nedovolilo mi to.. zistil som ze take nieco sa nesmie ..heh aspon nieco som sa z toho celeho naucil
A inac to ani netusim kolko inych sprievodnych chyb toto cele napacha.. nevraviac o tom ze tam zavadzam jeden for navyse, ten for k:=... s tym to uz asi nebude quicksort jak by mal byt

Proste cele si to viac a viac komplikujem.. a to nemam doriesene asi ani celu tu vec okolo rekurzie.. co sa tyka toho primarneho rozdelenia pola na cast s cislami vacsimi ako pivot a cast s cislami mensimi, napadlo na vytvorit dva polia (alebo jedno s dvojakym indexom) kde by sa zapisovali hodnoty, ktore su vacsie ako pivot a tie mensie do druheho, a potom sa to proste hodi do spolocneho pola ako sa ma, ale to berie pamat a urcite sa to tak nema robit, take nieco nam profesor nehovoril.. i ked cele by som to tak asi vyriesil

ono by to vypadalo takhle:

pole: 1 2 3 0 4 5 6 --- pivot -> 0
hledame co tam nepatri z leva: nepatri 1 a z prava bys jel az k 0... a prohodil je...
dalsi kolo: nepatri tam 2... z prava jdes ak ke 2 ale ta tam jeste patri ... takze mas indexy <1; 1> tj jeden prvek
a pak ten zbytek...

snad tam nemam nejakou chybu z toho ze bych to nejak spatne pochopil sam :D
urcite bys mel minimalne neco prohodit pokud si nasel jednu hodnotu co tam nepatri... treba zrovna s tim pivotem...
jinak by byla sranda kdyby ti jedno vyslo prazdna mnozina a druhe zase to same jako pred tim :DDD

To KIIV : "hledame co tam nepatri z leva: nepatri 1 a z prava bys jel az k 0... a prohodil je... " cize ty myslis ze ked nenajde na oboch stranach nieco na prehodenie, napriklad leen na jednej, tak potom toho osameleho ma prehodit so samotnym pivotom? no neviem ci tomu verim..

tiez som nepochopil tie indexy <1;1> co znamenaju, v tvojom poli dojdeme hned po prvom kole ku stavu 0 2 3 1 4 5 6 a hotovo, nebolo by co riesit, vsetko vacsie ako pivot 0 je napravo od neho.. :)

Ale skusil som si odsimulovat tvoj postup napr na poli 9 8 4 5 6 8 9.. pivot je 5..

9 8 4 5 6 8 9
1. kolo - 9 na prehodenie, sprava az po pivota nic, tak davaj, prehod s pivotom:
5 8 4 9 6 8 9
2. kolo - 8 je v pohode, nic
3. kolo - 4 na prehodenie, mala by ist dolava, nie je nic co by trebalo premistnit z lava doprava takze 4ku dame za pivota:
4 8 5 9 6 8 9
Dalsie prvky - 9,6,8,9 su k pivotovi umiestnene spravne, takze hotovo.. a co z toho vzniklo? nalavo od pivota mame ! 8micku !
To asi bude zle.. :D

Zkusím ten algoritmus popsat trochu jinými slovy.

Procedura:
Vstupní parametry: indexy Začátek a Konec, které určují, jaký úsek pole chci třídit.
Lokální proměnné: pomocné indexy Levý, Pravý a Pivot.

Index Levý umístím na pozici Začátek, Pravý na Konec a Pivot na (Začátek+Konec) div 2 (tedy někam do poloviny tříděného úseku).
Cyklus:
Levý index postupně zvětšuji (tj. posouvám v poli doprava) do okamžiku, kdy buď narazím na prvek větší než prvek na indexu Pivot nebo dokud s Levým nedojedu až k Pivotu (takže Levý buď ukazuje na ten špatně umístěný prvek, nebo se rovná Pivotu).
To samé s Pravým, jenom posouvám doleva a ne doprava.
Pokud Levý<>Pravý, vyměním prvek na pozici Levého s prvkem na pozici Pravého (indexy Levý a Pravý se nemění). Navíc pokud Pivot=Levý, tak Pivot:=Pravý nebo pokud Pivot=Pravý, tak Pivot:=Levý (takže Pivot ukazuje stále na stejný prvek).
Celý tenhle Cyklus opakuji až do okamžiku, kdy Levý=Pravý=Pivot.

Pokud jsou před Pivotem ještě alespoň 2 prvky (tedy Pivot-Začátek>=2), zavolám rekurzivně tuhle proceduru na úsek Začátek..Pivot-1.
Pokud jsou za Pivotem ještě alespoň 2 prvky (tedy Konec-Pivot>=2), zavolám rekurzivně tuhle proceduru na úsek Pivot+1..Konec.

Konec procedury.


Nejdůležitější je:
- Index Levý musí být vždy vlevo od Pravého nebo nanejvýš shodný.
- Index Pivot musí ukazovat stále na stejný prvek (pokud se ten prvek přemístí, přemístí se tedy i Pivot).
- Pivot musí být neustále mezi Levým a Pravým nebo nanejvýš shodný s některým z nich.
- Po doběhnutí jednoho Cyklu jsou vlevo od Pivotu prvky menší nebo stejné než prvek na Pivotu, vpravo větší nebo stejné.

Fungovat to bude i v případě, že Pivot skončí někde na kraji pole - v takovém případě se pak procedura rekurzivně zavolá jenom na tu stranu, na které ještě něco zbylo (vliv to má pouze na efektivitu, ne na proveditelnost - ta je vždycky zaručená).

jenze ta osmicka nalevo od pivota je taky moc velka a musi se hodit jinam
pivot se dava do samostatne promenne aby se ti v prubehu prohazovani nezmenil...

9 8 4 5 6 8 9

z leva nepatri hned 9  left_index=0  

z prava nepatri pivot 5 right_index=3

prohodi se:

5 8 4 9 6 8 9



dalsi kolo:

zleva nepatri 8  (left_index=1)

z prava nepatri 4 (right_index=2)

prohodi se:

5 4 8 9 6 8 9



dalsi kolo:

z leva nepatri 8    left_index=2

z prava nepatri 4   right_index=1

indexy se ale uz prekryvaji takze je na case koncit...



a dalsi iterace:

qsort( zacatek, right_index );  (* zatim  0, 1 *)

qsort( left_index, konec );  (* zatim 2, 6 *)



EDIT:  jo a aby se to nezacyklilo tak dat pred dalsi iteraci   if  ( zacatek < right_index )  qsort( zacatek, right_index );

to podobne u druhe poloviny... aby se skoncilo kdyz je tam jen jeden prvek :D

To KIIV : tak po prve.. z tvojho vysvetlenia v riadkoch 8 az 12 som fakt mimo.. tvrdis ze
" zleva nepatri 8 (left_index=1)
z prava nepatri 4 (right_index=2) "

Ale ako?
1. Tak bud to cele tvrdis vzhladom k povodnej postupnosti 9 8 4 5 6 8 9, ale vzhladom na pivota 5 to neje pravda pre 4ku
2. Alebo to tvrdis vzhladom na uz zmenenu postupnost 5 8 4 9 6 8 9 a v tej ci uz povazujes za pivota 5 alebo 9 je osmicka v poriadku, nevidim dovod ju menit, je napravo od 5 i nalavo od 9
3. Alebo to tvrdis tak, ze povazujes za pivota 5 v takom zmysle, ze je v nejakej osobitnej premennej, s ktorou to porovnavas a pritom beries do uvahy POVODNY INDEX PIVOTA ((zaciatok + konec) div 2, co sa rovna 4), tak potom vtedy by ta 8micka mala byt prenesena, ale 4ka je aj tak v poriadku

Problem vidim v tom ze cele to pole sa presuvanim toho pivota velmi meni, nikdy neviem co vzhladom naco mam porovnavat v kazdom momente sa situacia meni..
Skusim este postudovat postup od Microsofta, mozno sa mi vyjasni..

jeste si nepochopil ...
pivot se vybere na zacatku a uz se nezmeni... nesmi se zmenit jinak je to nesmyslne razeni...

nalevo tam nepatri cokoliv co je VETSI NEZ PIVOT
napravo tam nepatri cokoliv co je MENSI NEZ PIVOT
pivot je vybran na zacatku a uz se NEMENI .. nesmi, jinak je to kravina...

kdyz to prohazes tak aby nalevo bylo vse mensi nez pivot a napravo vse vetsi rovno pivotu


to hledani co tam nepatri nalevo a napravo se opakuje dokud nejsme uz v druhe casti

na wiki je ukazka kodu.. akorat asi globalni pole... coz je prasecina: http://cs.wikipedia.org/wiki/Quicksort

jo abych to jeste ujasnil s PIVOTEM...

ser na index kde je....
pivot se MUSI ULOZIT DO PROMENNE ... treba promenna PIVOT a s ni se to pak srovnava...
to ze byl pivot na nejakym indexu kdo vi kde me naprosto nezajima

no a nejlepe je to koukam znazorneno:

To Mircosoft : V tvojom postupe si to pekne opísal všetko sa mi páči, aj ma vlastne napadlo nieco zo toho, ze chybu som robil aj v tom ze som asi mal pouzit repeat namiesto for..

Ale vidim v tom stale tu istu dieru co riesim s KIIV.. vysvetli mi prosim tento usek, ked sa dostavame do fazy ked Levy alebo Pravy je uz totozny s Pivotom:
"Navíc pokud Pivot=Levý, tak Pivot:=Pravý nebo pokud Pivot=Pravý, tak Pivot:=Levý (takže Pivot ukazuje stále na stejný prvek)."

Najprv, neviem ci v tych priradeniach myslis indexy alebo hodnoty.. Ak ma pivot ukazovat stale rovnaku hodnotu/prvok, tak potom skromne dedukujem ze sa tu asi menia iba tie indexy, co sa mi paci, lebo pivotovi sa raz index zmenit musi ked berieme do uvahy ze pravdepodobne sme sa asi tazko vybranim prostredneho indexu (zac + kon)div 2 mohli zaroven trafit prostrednu hodnotu.. Ale ako potom dosiahneme podmienku Levy=Pivot=Pravy, ak index pivota zmenime?

Alebo mozno by ten index mal zostat tak, len hodnota sa prehodi a potom by asi trebalo zabezpecit aby tie zvysne prvky ktore este maju byt kontrolovane az kym aj ich pohyblivy index nedojde k pivotovi, aby tie boli teraz porovnavane s hodnotu toho prehodeneho pivota(stacilo by porovnavat s nejakou premennou s kopiou pivotovej hodnoty). Vtedy vsak moze nastat ze nasledujuci prvok je k pivotovi orientovany spravne, dalsi nespravne, tym padom sa pivot vdaka tomu druhemu opat prehodi a teraz sa dostane do zlej polohy vzhladom k tomu prvemu ku ktoremu bol este vtedy spravne a uz sa nanho zabudne lebo sa k nemu vracat nebudeme .. vid priklad 9 8 4 5 6 8 9

Mozno by si si sam mohol odsimulovat svoj postup na tom priklade, a daj vediet co ti tvojim postupom vyslo

To KIIV : tak ten obrazok ukazuje len rekurziu samtonu, o zoradeni tam nevidim nic..

Dobre Pivot je v osobitnej premennej a len s nim sa to bude porovnavat, ale aj tak aj on na konci toho vsetkeho musi mat nejaku poziciu, aj on sa niekde musi presunut. A PRAVE TOTO tu vidim ako problem..

kontrolujes jen pokud je v levo vetsi nez pivot a na pravo mensi nez pivot.... zadna ekvivalence v tom neni

ty kokos ja sa idem zblaznit.. som sa vzdal a pozrel som si to na tej wikipedii.. ked som cital tu jednoduchu procedurku tak som mal usta dokoran a ze WAW.. :D ono to funguje finta je v tom ze ked uz tu 5ku, toho pivota prehodim tak sa pokracuje aj v kontrole za povodnym indexom pivota a tam sa to tiez moze a nemusi prehadzovat podla velkosti pivota a vsetko to skonci tak ze sa indexy dostanu za seba, prejdu popri sebe a vsetko je v tom momente rozmiestnene tak ako treba, cize staci vziat tie indexy do rekurzie ako koncove body a nestarat sa o nic ! normalne som stastny teraz ked to viem :D

Diky za trpezlivost s mojimi nazormi.. vsetko je to vlastne o uhle pohladu.. ja som nato cely cas isiel zle.. nikdy som sa nato nepozrel takto ako to je na wikipedii .. stacilo to nekomplikovat, byt jednoduchy :)

a copak sem nerikal ze se jede dokud nejsou indexy pres sebe ? :D

yuchuu uz mi to ide aj v pascalee :D no pisal ale ja som stale zil s tym mojim forom, a ze sa ide po polku pola z jednej i z druhej strany.. repeat to je celkom ina pesnicka a este v takom style ako to je na wiki ... ja normalne placem od radosti :DD