sort method
void
sort()
Sort the elements in the sweep and prune
Implementation
void sort() {
int count = 0;
int threshold = 1;
while((numElements >> threshold) != 0 ){
threshold++;
}
threshold = threshold * numElements >> 2;
count = 0;
bool giveup = false;
Map<int,SAPElement?> elements = this.elements;
for(int i = 1; i < numElements; i++){ // try insertion sort
SAPElement? tmp=elements[i];
double pivot=tmp?.value ?? 0;
SAPElement? tmp2=elements[i-1];
double pivot2=tmp2?.value ?? 0;
if(pivot2 > pivot){
int j=i;
do{
elements[j]=tmp2;
if(--j==0)break;
tmp2=elements[j-1];
pivot2=tmp2?.value ?? 0;
}while(pivot2 > pivot);
elements[j]=tmp;
count+=i-j;
if(count>threshold){
giveup=true; // stop and use quick sort
break;
}
}
}
if(!giveup)return;
count=2;
List<double> stack = this.stack;
stack[0]=0;
stack[1]=numElements-1;
while(count>0){
int right=stack[--count].toInt();
int left=stack[--count].toInt();
int diff=right-left;
if(diff>16){ // quick sort
//var mid=left+(diff>>1);
int mid = left + ((diff*0.5).floor());
SAPElement? tmp = elements[mid];
elements[mid] = elements[right];
elements[right] = tmp;
double pivot = tmp?.value ?? 0;
int i = left-1;
int j = right;
while( true ){
SAPElement? ei;
SAPElement? ej;
do{ ei = elements[++i]; } while(ei != null && ei.value < pivot);
do{ ej = elements[--j]; } while(ej != null && pivot < ej.value && j != left );
if(i >= j) break;
elements[i] = ej;
elements[j] = ei;
}
elements[right] = elements[i];
elements[i] = tmp;
if( i - left > right - i ) {
stack[count++] = left.toDouble();
stack[count++] = i - 1;
stack[count++] = i + 1;
stack[count++] = right.toDouble();
}
else{
stack[count++] = i + 1;
stack[count++] = right.toDouble();
stack[count++] = left.toDouble();
stack[count++] = i - 1;
}
}
else{
for(int i = left + 1; i <= right; i++ ) {
SAPElement? tmp = elements[i];
double pivot = tmp?.value ?? 0;
SAPElement? tmp2 = elements[i-1];
double pivot2 = tmp2?.value ?? 0;
if( pivot2> pivot) {
int j = i;
do{
elements[j] = tmp2;
if( --j == 0 ) break;
tmp2 = elements[j-1];
pivot2=tmp2?.value ?? 0;
}while( pivot2> pivot );
elements[j] = tmp;
}
}
}
}
}