By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
 429,384 Members | 927 Online + Ask a Question
Need help? Post your question and get tips & solutions from a community of 429,384 IT Pros & Developers. It's quick & easy.

# QuickSort . I don't understand this behavior

 P: n/a Hi, I want to sort an array of pointers, each position of this array point to a position in an integer array. There is a strange behavior when the 'pivot' is '0'. I am using Visual C++, and when executing the OS tell me "quicksort.exe has encountered a problem and needs to close". When there is no zeros in the integer array, this doesn't happen. The pivot is always the last element. Try to change the last element in the array for a non zero value and you will se it works. Tell me something please. Thanks #include using namespace std; int *buffer; int array = {4,1,14,9,2,3,6,11,8,0}; void quicksort(int **vector, int inf, int sup) { int *temp; int pivot = *vector[sup]; int i = inf-1; int j = sup; int cont = 1; if(inf>=sup) return; cout << "pivot " << pivot << endl; while(cont) { while(*vector[++i] < pivot); while(*vector[--j] > pivot); if(i < j) { temp = vector[i]; vector[i] = vector[j]; vector[j] = temp; } else cont = 0; } temp = vector[i]; vector[i] = vector[sup]; vector[sup] = temp; quicksort(vector, inf, i-1); quicksort(vector, i+1, sup); } int main() { for(int i=0; i<10; i++) buffer[i] = &array[i]; for(i=0; i<10; i++) cout << *buffer[i] << " "; cout << endl; quicksort(buffer, 0, 9); cout << "Sorted array : " << endl; for(i=0; i<10; i++) cout << *buffer[i] << " "; cout << endl; return 0; } Apr 24 '06 #1
Share this Question
2 Replies

 P: n/a -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 camotito wrote: Hi, I want to sort an array of pointers, each position of this array point to a position in an integer array. There is a strange behavior when the 'pivot' is '0'. I am using Visual C++, Sorry, but C++ is off topic in comp.lang.c You might want to try comp.lang.c++ and when executing the OS tell me "quicksort.exe has encountered a problem and needs to close". When there is no zeros in the integer array, this doesn't happen. The pivot is always the last element. Try to change the last element in the array for a non zero value and you will se it works. Tell me something please. Thanks #include [snip] Yup. Definitely not C - -- Lew Pitcher, IT Specialist, Corporate Technology Solutions, Enterprise Technology Solutions, TD Bank Financial Group (Opinions expressed here are my own, not my employer's) -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.2.2 (MingW32) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFETPWgagVFX4UWr64RAinNAKDJ6CTecHbTbcFKZEfh4i n/ZtC1GwCgur1R dUDzcfgJRmVQQdjO3xJ9jlM= =wb/c -----END PGP SIGNATURE----- Apr 24 '06 #2

 P: n/a camotito schrieb: Hi, I want to sort an array of pointers, each position of this array point to a position in an integer array. There is a strange behavior when the 'pivot' is '0'. I am using Visual C++, and when executing the OS tell me "quicksort.exe has encountered a problem and needs to close". When there is no zeros in the integer array, this doesn't happen. The pivot is always the last element. Try to change the last element in the array for a non zero value and you will se it works. Tell me something please. Thanks I will ignore the C++ specific stuff; read the comp.lang.c++ FAQ or post your code for code review to comp.lang.c++ -- your code leaves much room for improvement. Your problem is that you do not control the indices. Print the indices within the corrected loops and at the beginning of quicksort to see what is going wrong. void quicksort(int **vector, int inf, int sup) { int *temp; int pivot = *vector[sup]; You are accessing vector[sup] without having checked whether sup >= inf. int i = inf-1; int j = sup; int cont = 1; if(inf>=sup) return; while(cont) { while(*vector[++i] < pivot); while(*vector[--j] > pivot); while (i < j && *vector[++i] < pivot); while (i < j && *vector[--j] > pivot); if(i < j) { temp = vector[i]; vector[i] = vector[j]; vector[j] = temp; } else cont = 0; } temp = vector[i]; vector[i] = vector[sup]; vector[sup] = temp; quicksort(vector, inf, i-1); quicksort(vector, i+1, sup); quicksort(vector, inf, i > inf ? i-1 : inf); quicksort(vector, i < sup ? i+1 : sup, sup); } Cheers Michael -- E-Mail: Mine is an /at/ gmx /dot/ de address. Apr 24 '06 #3

### This discussion thread is closed

Replies have been disabled for this discussion. 