"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message

news:3F***************@gascad.at...

consider your array to sort consists of just 2 numbers

5 5

what will be the value of val?

a[left] / 2 -> 5 / 2 -> 2

a[right] / 2 -> 5 / 2 -> 2

val therefore will get a value of 4

now look at the while loops

while( a[--rm] > val);

that loop will sure run out of bounds

while( a[++lm] < val);

again: out of bounds

Out of bounds may mean in this case: outside the

range left-right. The partition function then swaps

some array elements it shouldn't, which will influence

the whole algorithm.

The problem is, that with the calculation you do, you may end up

with a number for val which is not even in the boundaries of the

numbers you try to sort (Sorry: I am not a native english speaker

so the above may sound confusing, but I don't know how to express

it better).

One technique I learned for comming up with a value for that trashold

value is something like this:

take a[left], a[right], a[(left+right)/2] and discard the smallest

and highest value (sort them and take the second in sorting order)

--

Karl Heinz Buchegger

kb******@gascad.at

Thanks Karl...this modification fixes the bug....and maintains the speed

boost ;-) good job to us both!!!!

#include <iostream>

const int kSMALL_ENOUGH = 16; //when to call selection-sort

using namespace std;

void fillRND(unsigned int* a, int size);

void showit(unsigned int* a, int size);

void quicksort(unsigned int* a, int left, int right);

int partition(unsigned int* a, int left, int right);

void selectionsort(unsigned int* a, int left, int right);

int verify(unsigned int* a, int size);

//unsigned int triplet(unsigned int* a, int left, int right);

int main(){

int clo;

cout << "Enter the number of elements to be sorted. ";

int sz;

cin >> sz;

unsigned int* a = new unsigned int[sz];

cout << "generating data...";

fillRND(a, sz);

cout << "done\nchecking data...";

verify(a, sz);

//showit(a, sz);

clo=clock();

cout << "sorting data...";

quicksort(a, 0, sz-1);

cout << "done in " << clock() - clo << " (ms)\nchecking data...";

verify(a, sz);

//showit(a, sz);

delete [] a;

system("pause");

return 0;

}

void quicksort(unsigned int* a, int left, int right){

if(left + kSMALL_ENOUGH < right) {

int split_pt = partition(a,left, right);

quicksort(a, left, split_pt);

quicksort(a, split_pt+1, right);

}else selectionsort(a, left, right);

}

int partition(unsigned int* a, int left, int right){

unsigned int val = a[left]/2 + a[right]/2;// = triplet(unsigned int* a,

int left, int right);

unsigned int x = a[left];

unsigned int z = a[right];

if(x < val)

if(val < z); //val = y; //x < y < z

else if(x < z) val = z; //x < z < y

else val = x; //z < x < y

else if(z < val); //val = y; //z < y < x

else if(z < x) val = z; //y < z < x

else val = x; //y < x < z

int lm = left-1;

int rm = right+1;

for(;;){

while(a[--rm] > val);

while(a[++lm] < val);

if(lm < rm){

unsigned int temp = a[rm];

a[rm] = a[lm];

a[lm] = temp;

}else return rm;

}

}

void selectionsort(unsigned int* data, int left, int right){

for(int i = left; i < right; ++i) {

int min = i;

for(int j=i+1; j <= right; ++j)

if(data[j] < data[min]) min = j;

unsigned int temp = data[min];

data[min] = data[i];

data[i] = temp;

}

}

int verify(unsigned int* a, int size){

for(int i = 0; i<size-1; ++i){

if(a[i] > a[i+1]){

cout << "numbers not sorted\n";

return 1;

}

}

cout << "numbers are sorted\n";

return 0;

}

void fillRND(unsigned int* a, int size){

srand(time(0));

int bits = (CHAR_BIT * sizeof(int))/2;

for(int i = 0; i < size; ++i)

a[i] = rand() + (rand() << bits); //to fill more than 15 bits...

}

void showit(unsigned int* a, int size){

for(int i = 0; i < size; ++i)

cout << i << ' ' << a[i] << endl;

cout << endl;

}