Trying to prevent my brain shrinking even smaller than its present size while sat here 'home alone' (i.e. feeling cerebrally challenged at the moment, make of that what you will), here's a little something to challenge the ql-users grey matter.
Many of you will be familiar with the Quicksort recursive sorting routine. I wanted to sort large amounts of data at one stage and compiled a program containing a recursive routine, which quickly ran out of stack space for all the recursion it needed. 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). The obvious starting point is to set stack_left(1) = 0 in line 190, but that leads to all sorts of errors under some circumstances such as data to be sorted already being in sorted order. Basically, like all Quicksorts the array to be sorted is split into "left" and "right" sections by choosing a median value and adjusting section pointers. An artificial stack is set up to remember pairs of pointers as required. Improved versions welcome! I know ql-users are always up to a challenge...I just hope poor Marcel doesn't end up spending days on it just because it's a "challenge" as usual ;-) 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) = 20-a 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 STOP -- Dilwyn Jones _______________________________________________ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
