As a programming exercise, I was playing with the quicksort algorithm.
The commented line in the "partition" function speeds things up a
bit. However, when used on (my machine) arrays larger than about
5,000,000 elements, the sort appears to freeze. I don't understand
this behavior. With this line commented as shown, the sort works fine
up to available memory (circa 50,000,000 elements, (200MB) on my 256MB
machine). I'm guessing the error has to do with "val" taking a
minimum or maximum value, but I can't fugure it out. If this Q is
off-topic to c++ and more appropriate on an "algorithm-oriented"
newsgroup, I apologize in advance.
Thanks,
Joe
#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);
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
;//<---note end of line here!
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;
}
