Dilwyn Jones writes: <> > So here's my attempt at a non-recursive version which probably defeats > the object (apart from not making QLiberator fall over with the stack > space demands). > > I got this working some time ago, apart from not being able to make it > handle subscript 0 of the array being sorted - you'll see what I mean > when you run it. (if you've never transferred a listing from email to > Superbasic before, just highlight, copy and save the listing as an > ascii or text file and transfer it to the QL ready to load in the > usual way, or ask me to email it to you as an attachment if easier).
There are lots of non-recursive quicksort algorithms available on the internet. None of the ones I found seem to include the zero'th element in the sort. Presumably this is because that would require an extra test in one of the inner loops, which is expensive. If you absolutey must have it, why not just use a workaround, as suggested below? 100 REMark Non-recursive quicksort routine 110 REMark adapted from standard Quicksort by Dilwyn Jones 120 REMark sorts elements 1 to "highest_entry" 130 REMark (i.e. doesn't *yet* manage to sort subscript 0 too) 140 : 150 highest_entry = 20 : DIM array(highest_entry) 160 FOR a = 0 TO highest_entry : array(a) = RND(0 TO 100) 170 : 180 stack_length = 12 : DIM stack_left(stack_length),stack_right(stack_length) 190 stack = 1 : stack_left(1) = 1 : stack_right(1) = highest_entry 200 REPeat outer 210 REMark take top entry from stack 220 left = stack_left(stack) : right = stack_right(stack) : stack = stack - 1 230 REMark split array 240 REPeat middle 250 pointer1 = left : pointer2 = right : med_value = array(INT((left+right)/2)) 260 REPeat inner 270 REPeat loop1 : IF array(pointer1) < med_value THEN pointer1 = pointer1 + 1 : ELSE EXIT loop1 280 REPeat loop2 : IF med_value < array(pointer2) THEN pointer2 = pointer2 - 1 : ELSE EXIT loop2 290 IF pointer1 <= pointer2 THEN 300 w = array(pointer1) : array(pointer1) = array(pointer2) : array(pointer2) = w 310 pointer1 = pointer1 + 1 : pointer2 = pointer2 - 1 320 END IF 330 IF pointer1 > pointer2 THEN EXIT inner 340 END REPeat inner 350 IF pointer1 < right THEN 360 REMark stack request to sort right partition 370 stack = stack+1 : stack_left(stack) = pointer1 : stack_right(stack) = right 380 END IF 390 right = pointer2 400 IF left >= right THEN EXIT middle 410 END REPeat middle 420 IF stack = 0 THEN EXIT outer 430 END REPeat outer 440 : 450 CLS: PRINT !array!\\ 460 : 470 t = array(0) 480 FOR i% = 1 TO DIMN(array) 490 IF t > array(i%) THEN 500 array(i% - 1) = array(i%) 510 ELSE 520 array(i% - 1) = t 530 EXIT i% 540 END IF 550 END FOR i% 560 IF i% = DIMN(array): array(DIMN(array)) = t 570 : 580 PRINT !array!\\ 590 : 600 STOP Per _______________________________________________ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
