qsort

[WayneA]

Code Select Expand

//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;
}