Sorting 2 variables: one ascending, one descending

[Meg]

Here's my entry. This code performs a QuickSort on the data using LastName & (100-Age) as the sort key.

NOTE: The QuickSort algorithm is largely not my own original code, I took an existing QuickSort algorithm and changed a few things in it.

EDIT: I have changed a 100 to 99 in my code, as per Neo's suggestion in the thread below. I do not deserve the credit for this.

*peace*

Meg.


[syntax="QBASIC"]DECLARE SUB QuickSort (SortArray() AS ANY, Low AS INTEGER, High AS INTEGER)

CLS

'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'Record declaration as given by challenge.
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
TYPE PersonType
LastName AS STRING * 10
Age AS STRING * 2
SortKey AS STRING * 12
END TYPE

'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'How many records of sample data are we reading?
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
MaxPeople% = 14

'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'Pull the sample data into an array
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
DIM People(1 TO MaxPeople%) AS PersonType
FOR i% = 1 TO MaxPeople%
READ People(i%).LastName, People(i%).Age

'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'Since we want ages sorted in reverse order, subtract their age from 99
'Check for single and double digits to be safe.
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
IF VAL(People(i%).Age) > 89 THEN
SortAge$ = "0" + LTRIM$(RTRIM$(STR$(99 - VAL(People(i%).Age))))
ELSE
SortAge$ = LTRIM$(RTRIM$(STR$(99 - VAL(People(i%).Age))))
END IF

'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'Create the sort key by concatenating Name and SortAge$
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
People(i%).SortKey = People(i%).LastName + SortAge$
NEXT i%

'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'Perform a QuickSort on the array, using the SortKey as an index.
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
QuickSort People(), 1, MaxPeople%

'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'Print the resulting array
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
FOR i% = 1 TO MaxPeople%
PRINT People(i%).LastName; People(i%).Age
NEXT i%

SYSTEM

'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'Sample Data
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

DATA Williams, 7
DATA Baker, 45
DATA Williams, 12
DATA Adams, 10
DATA Dillon, 12
DATA Williams, 8
DATA "Bloom, Jr.", 18
DATA Connor, 50
DATA Albright, 12
DATA Connor, 1
DATA Williams, 8
DATA Dillon, 78
DATA Connor, 99
DATA Williams, 99

SUB QuickSort (SortArray() AS PersonType, Low AS INTEGER, High AS INTEGER)

DIM Lower AS INTEGER
DIM Higher AS INTEGER
DIM RandIndex AS INTEGER
DIM Partition AS STRING * 12

'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'Quicksort selects a pivot point, putting smaller elements on one side and
'larger elements on the other. Then it calls itself recursively on each
'side. It repeats this until each subdivion contains at most 2 elements.
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

IF Low < High THEN

'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'At this point, only two elements remain in the subdivision. Sort
'them, and end the recursion line.
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

IF High - Low = 1 THEN
IF SortArray(Low).SortKey > SortArray(High).SortKey THEN
SWAP SortArray(Low), SortArray(High)
END IF

ELSE

'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'Pick a random pivot
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

RandIndex = INT(RND * (High - Low + 1)) + Low
SWAP SortArray(High), SortArray(RandIndex)
Partition = SortArray(High).SortKey
DO

'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'Move in from both sides towards the pivot
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

Lower = Low
Higher = High
DO WHILE (Lower < Higher) AND (SortArray(Lower).SortKey <= Partition)
Lower = Lower + 1
LOOP

DO WHILE (Higher > Lower) AND (SortArray(Higher).SortKey >= Partition)
Higher = Higher - 1
LOOP

'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'If we hit the pivot, the two elements on either side
'are out of order. Swap them.
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

IF Lower < Higher THEN
SWAP SortArray(Lower), SortArray(Higher)
END IF

LOOP WHILE Lower < Higher

'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'Move the pivot back to its proper place
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

SWAP SortArray(Lower), SortArray(High)

'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'Recursively call the sort, passing the smaller subdivision
'first to save stack space
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

IF (Lower - Low) < (High - Lower) THEN
QuickSort SortArray(), Low, Lower - 1
QuickSort SortArray(), Lower + 1, High
ELSE
QuickSort SortArray(), Lower + 1, High
QuickSort SortArray(), Low, Lower - 1
END IF
END IF
END IF

END SUB[/syntax]