January 26, 2023, 10:40:49 PM

News:

IonicWind Snippit Manager 2.xx Released!  Install it on a memory stick and take it with you!  With or without IWBasic!


qsort

Started by WayneA, June 14, 2010, 02:20:37 PM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

WayneA

//export qsort;

int a[100];

sub main(){
int i;
for(i=0;i<100;i++){
a[i]=rnd(1)*99;
}
qsort(0,99,a);
for(i=0;i<100;i++){
print(a[i],"\t",);
}
do{}until getkey()!="";
return;
}

sub qsort(int qsleft,int qsright,int qsdata[]){
int nleft,nright,cent;
int dumswap,ctrv;

if(qsleft<qsright){
cent=(qsleft+qsright)/2;
ctrv=qsdata[cent];
//{swapping qsdata[qsright] and qsdata[cent]
dumswap=qsdata[qsright];
qsdata[qsright]=qsdata[cent];
qsdata[cent]=dumswap;
//}
nleft=qsleft;
nright=qsright;

while(nleft<nright){
//look for a value left of center that belongs on the right.
while(nleft<nright and qsdata[nleft]<=ctrv){
nleft++;
}

//right of center now
while(nright>nleft and qsdata[nright]>=ctrv){
nright--;
}

//if nleft is less than nright then we need to swap these values.
if(nleft<nright){
//{swapping qsdata[nright] and qsdata[nleft]
dumswap=qsdata[nright];
qsdata[nright]=qsdata[nleft];
qsdata[nleft]=dumswap;
//}
}
}
//{swapping qsdata[qsright] and qsdata[nleft]
dumswap=qsdata[qsright];
qsdata[qsright]=qsdata[nleft];
qsdata[nleft]=dumswap;
//}

//recursively call qsort, moving towards the center of the array until everything is sorted
if((nleft-qsleft)<(qsright-nleft)){
qsort(qsleft,nleft-1,qsdata);
qsort(nleft+1,qsright,qsdata);
}
else{
qsort(nleft+1,qsright,qsdata);
qsort(qsleft,nleft-1,qsdata);
}
}
return;
}
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code...

All code I post is in the public domain.