454,952 Members | 1,424 Online
Need help? Post your question and get tips & solutions from a community of 454,952 IT Pros & Developers. It's quick & easy.

# the quicksort algorithm in Numerical Recipes in C (2nd edition)

 P: n/a Hi, I'm wondering if anybody has ever copied the quicksort algorithm from the book Numerical Recipes in C: The Art of Scientific Computing (2nd ed.), by Press, Teukolsky, Vetterling, and Flannery, in Chapter 8. Quicsort is supposed to sort an array of, say, doubles, in ascending order. I tried to copy this algorithm line by line to test it. It seems that there's an error in this algorithm as given in this book. Namely, the first two entry (0th entry) of the array is never moved, and the 2nd entry (1st entry) is also set to 0 after the sorting was supposed to be completed. All other entries seemed to be correctly updated. I'm wondering if anybody on this forum's ever had the same problem when using this algorithm taken from this book. If so, could you tell me what the problem is and how to fix it? I'm a little time-pressed to investigate this myself. Thanks in advance. -Ed ------------------------------------------------------------------ To give an example of this error, I have an initial array of 20 doubles as follows: sample_array[0] = 5.754104 sample_array[1] = 0.973984 sample_array[2] = 14.586500 sample_array[3] = 11.796852 sample_array[4] = 4.032750 sample_array[5] = 0.618612 sample_array[6] = 8.638782 sample_array[7] = 2.309558 sample_array[8] = 4.144175 sample_array[9] = 15.159169 sample_array[10] = 1.541796 sample_array[11] = 18.063583 sample_array[12] = 4.739992 sample_array[13] = 4.905477 sample_array[14] = 8.836610 sample_array[15] = 15.108313 sample_array[16] = 18.243906 sample_array[17] = 14.667340 sample_array[18] = 5.801667 sample_array[19] = 2.857230 And after the sorting, it becomes: sample_array[0]=5.754104 sample_array[1]=0.000000 sample_array[2]=0.618612 sample_array[3]=0.973984 sample_array[4]=1.541796 sample_array[5]=2.309558 sample_array[6]=2.857230 sample_array[7]=4.032750 sample_array[8]=4.144175 sample_array[9]=4.739992 sample_array[10]=4.905477 sample_array[11]=5.801667 sample_array[12]=8.638782 sample_array[13]=8.836610 sample_array[14]=11.796852 sample_array[15]=14.586500 sample_array[16]=14.667340 sample_array[17]=15.108313 sample_array[18]=15.159169 sample_array[19]=18.063583 Nov 15 '05 #1
5 Replies

 P: n/a Please ignore this question. I figured it out. -Ed On Wed, 26 Oct 2005, Edward Hua wrote: Hi, I'm wondering if anybody has ever copied the quicksort algorithm from the book Numerical Recipes in C: The Art of Scientific Computing (2nd ed.), by Press, Teukolsky, Vetterling, and Flannery, in Chapter 8. Quicsort is supposed to sort an array of, say, doubles, in ascending order. I tried to copy this algorithm line by line to test it. It seems that there's an error in this algorithm as given in this book. Namely, the first two entry (0th entry) of the array is never moved, and the 2nd entry (1st entry) is also set to 0 after the sorting was supposed to be completed. All other entries seemed to be correctly updated. I'm wondering if anybody on this forum's ever had the same problem when using this algorithm taken from this book. If so, could you tell me what the problem is and how to fix it? I'm a little time-pressed to investigate this myself. Thanks in advance. -Ed ------------------------------------------------------------------ To give an example of this error, I have an initial array of 20 doubles as follows: sample_array[0] = 5.754104 sample_array[1] = 0.973984 sample_array[2] = 14.586500 sample_array[3] = 11.796852 sample_array[4] = 4.032750 sample_array[5] = 0.618612 sample_array[6] = 8.638782 sample_array[7] = 2.309558 sample_array[8] = 4.144175 sample_array[9] = 15.159169 sample_array[10] = 1.541796 sample_array[11] = 18.063583 sample_array[12] = 4.739992 sample_array[13] = 4.905477 sample_array[14] = 8.836610 sample_array[15] = 15.108313 sample_array[16] = 18.243906 sample_array[17] = 14.667340 sample_array[18] = 5.801667 sample_array[19] = 2.857230 And after the sorting, it becomes: sample_array[0]=5.754104 sample_array[1]=0.000000 sample_array[2]=0.618612 sample_array[3]=0.973984 sample_array[4]=1.541796 sample_array[5]=2.309558 sample_array[6]=2.857230 sample_array[7]=4.032750 sample_array[8]=4.144175 sample_array[9]=4.739992 sample_array[10]=4.905477 sample_array[11]=5.801667 sample_array[12]=8.638782 sample_array[13]=8.836610 sample_array[14]=11.796852 sample_array[15]=14.586500 sample_array[16]=14.667340 sample_array[17]=15.108313 sample_array[18]=15.159169 sample_array[19]=18.063583 Nov 15 '05 #2

 P: n/a Edward Hua writes: I'm wondering if anybody has ever copied the quicksort algorithm from the book Numerical Recipes in C: The Art of Scientific Computing (2nd ed.), by Press, Teukolsky, Vetterling, and Flannery, in Chapter 8. Copying code from that book is a mistake. The explanatory text can be insightful, but the code is not well written. -- "When I have to rely on inadequacy, I prefer it to be my own." --Richard Heathfield Nov 15 '05 #3

 P: n/a Edward Hua said the following, on 10/26/05 10:15: Hi, I'm wondering if anybody has ever copied the quicksort algorithm from the book Numerical Recipes in C: The Art of Scientific Computing (2nd ed.), by Press, Teukolsky, Vetterling, and Flannery, in Chapter 8. Quicsort is supposed to sort an array of, say, doubles, in ascending order. I tried to copy this algorithm line by line to test it. It seems that there's an error in this algorithm as given in this book. Namely, the first two entry (0th entry) of the array is never moved, and the 2nd entry (1st entry) is also set to 0 after the sorting was supposed to be completed. All other entries seemed to be correctly updated. I'm wondering if anybody on this forum's ever had the same problem when using this algorithm taken from this book. If so, could you tell me what the problem is and how to fix it? I'm a little time-pressed to investigate this myself. Thanks in advance. This really is not a C question as you have posed it, but I have a suspicion that you have a C-related problem. The original _Numerical Recipes_ book used FORTRAN, I think. I don't have my copy of it, or of _Numerical Recipes in C_, handy, but I seem to recall that in the C version the authors used some funky macro hacks so that they could use 1-origin arrays (a la FORTRAN), rather than C's 0-origin arrays. If you have an "off-by-one" problem related to this, it might account for both of the symptoms you are seeing: the zeroth element is never looked at; and the element 'array[20]' (which of course doesn't exist as far as C is concerned) _is_ used, and might be zero by chance. -- Rich Gibbs ri*****@gmail.com "You can observe a lot by watching." -- Yogi Berra Nov 15 '05 #4

 P: n/a Ok. Is there a more authoritative book/on-line refrence that has an archive of C functions (like those in NRiC)? Thanks. -Ed On Wed, 26 Oct 2005, Ben Pfaff wrote: Edward Hua writes: I'm wondering if anybody has ever copied the quicksort algorithm from the book Numerical Recipes in C: The Art of Scientific Computing (2nd ed.), by Press, Teukolsky, Vetterling, and Flannery, in Chapter 8. Copying code from that book is a mistake. The explanatory text can be insightful, but the code is not well written. -- "When I have to rely on inadequacy, I prefer it to be my own." --Richard Heathfield Nov 15 '05 #5

 P: n/a Edward Hua wrote: how to fix it? #define BYTE_SWAP(A, B) \ { \ p1 = (A); \ p2 = (B); \ end = p2 + size; \ do { \ swap = *p1; \ *p1++ = *p2; \ *p2++ = swap; \ } while (p2 != end); \ } void q2sort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *)) { unsigned char *left; size_t middle, last, right; struct { size_t bytes; void *base; } stack[CHAR_BIT * sizeof nmemb], *stack_ptr; unsigned char *p1, *p2, *end, swap; stack -> bytes = nmemb * size; stack -> base = base; stack_ptr = stack + 1; do { --stack_ptr; if (stack_ptr -> bytes > size) { left = stack_ptr -> base; right = last = stack_ptr -> bytes - size; middle = size; while (compar(left, left + middle) > 0 && middle != right) { middle += size; } while (compar(left + last, left) > 0) { last -= size; } while (last > middle) { BYTE_SWAP(left + middle, left + last); do { middle += size; } while (compar(left, left + middle) > 0); do { last -= size; } while (compar(left + last, left) > 0); } BYTE_SWAP(left, left + last); if (right - last > last) { stack_ptr -> base = left + last + size; stack_ptr++ -> bytes = right - last; stack_ptr -> base = left; stack_ptr++ -> bytes = last; } else { stack_ptr++ -> bytes = last; stack_ptr -> base = left + last + size; stack_ptr++ -> bytes = right - last; } } } while (stack_ptr != stack); } -- pete Nov 15 '05 #6

### This discussion thread is closed

Replies have been disabled for this discussion.