> Very quick response... you have the normal HUGE bug. When you split > the > array into a left and right chunk, you MUST stack the LARGER chunk, > and > sort the smaller one. That's why the stack space disappears. > > And... be very careful about what happens when you can have > duplicate > values... what happens as the indices cross over in the middle? I > think > your code tends to fail safe... with a slight cost in overall speed. > > Also... quicksort is NOT the fastest sort. Actually, bubblesort > beats it > for trivial cases. The choice of "median" value is not all that > significant, but just choosing the one in the centre isn't that > smart. > Personally, I tend to eliminate the cases with less than three items > as > special cases. I then "bubblesort" the one in the middle with the > ones > at the two extrema. If there are now only three elements, we're > done. > Otherwise, /now/ we can use the one in the middle as a better stab > at > the median, and actually start the swapping one in from each end. OK, I haven't taken much of a look at this. Here are a couple of recursive versions of the Quicksort.
The first one is slower - I think this is based on a listing I found in a magazine called Popular Computing Weekly years ago: 2380 DEFine PROCedure QUICKSORT1 (array$,bottom,top) 2390 LOCal sort_loop,low,high,ptr 2400 low = bottom : high = top : ptr = bottom 2410 REPeat sort_loop 2420 IF low >= high THEN EXIT sort_loop 2430 IF array$(low) > array$(high) THEN 2440 temp$ = array$(low) 2450 array$(low) = array$(high) 2460 array$(high) = temp$ 2470 IF ptr = low THEN 2480 low = low+1 : ptr = high 2490 ELSE 2500 high = high-1 : ptr = low 2510 END IF 2520 ELSE 2530 IF ptr = low THEN high = high-1 : ELSE low = low+1 2540 END IF 2550 END REPeat sort_loop 2560 IF ABS(top - bottom) < 2 THEN RETurn 2570 QUICKSORT1 array$,bottom,ptr - 1 2580 QUICKSORT1 array$,ptr + 1,top 2590 END DEFine QUICKSORT1 The second version is based on an early QL User, listing by Marcus Jeffrey. It differs in that it needs the last item in the array to be a "highest possible value". So if you have an array set up with DIM array(10) you can use elements 0 to 9 yourself and deliberately set element 10 to the maximum possible value so that it stays at the end of the array: 2610 REMark Quicksort, faster variety, by Marcus Jeffery 2620 : 2630 REMark prepare an array to sort, remembering that this routine needs 2640 REMark a predefined 'highest value entry' at the end of the array 2650 REMark QUICKSORT2 also needs the procedure QS2_PARTITION below 2660 DEFine PROCedure QUICKSORT2 (array,lower,upper) 2670 LOCal part_elem 2680 IF lower < upper THEN 2690 part_elem = upper + 1 2700 QS2_PARTITION lower,part_elem 2710 QUICKSORT2 array,lower,part_elem-1 2720 QUICKSORT2 array,part_elem+1,upper 2730 END IF 2740 END DEFine QUICKSORT2 2750 : 2760 DEFine PROCedure QS2_PARTITION (i,j) 2770 LOCal k,temp$,swap$,loop,inc_k,dec_j,swap 2780 temp$ = array(i) : k = i 2790 REPeat loop 2800 REPeat inc_k 2810 k = k + 1 2820 REMark this is where the 'guaranteed highest value' comes in 2830 IF array(k) >= temp$ THEN EXIT inc_k 2840 END REPeat inc_k 2850 REPeat dec_j 2860 j = j - 1 2870 REMark conversely we don't need a 'guaranteed less than' value 2880 REMark at the start of the array as the sorting process does 2890 REMark this for us anyway 2900 IF array(j) <= temp$ THEN EXIT dec_j 2910 END REPeat dec_j 2920 IF k < j THEN 2930 REMark swap the two entries around 2940 swap$ = array(k) : array(k) = array(j) : array(j) = swap$ 2950 ELSE 2960 EXIT loop 2970 END IF 2980 END REPeat loop 2990 array(i) = array(j) : array(j) = temp$ 3000 END DEFine QS2_PARTITION The second one is much faster than the first. Timing checks I did on it some time ago show that Quicksort is good on mixed random data, which is usually where other sort routines slow down. Where the data is in pretty good sorted order already, other sort routines can be faster. Quicksort is a reasonable choice as a general purpose sort routine where the data distributions and array sizes aren't really known in advance. Mark Knight sent QL Today a listing some years ago of a sort called pigeon sort, which could be faster than Quicksort but it was much longer than these listings and I couldn't understand it at the time. Improvement suggestions for the above listings welcome. -- Dilwyn Jones _______________________________________________ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
