Code: Select all
' Sort functions: BubbleSort and QuickSort
' by Dutchman » 24 May 2013
' Demoprogram for the iPad-app Smart-Basic
' original in Basic! 'by Dutchman 2012
' The functions operate on columns in numerical two-dimensional arrays (tables)
'
' UPDATED by Dutchman 7 July 2016
' QuickSort sorts a table of 10000 rows x 3 columns in 1.1 seconds
' on iPad-Air, iOS 9.3.2, SmartBasic 5.6
OPTION BASE 1 ' functions have to be adapted for BASE 0
DEF BubbleSort(Array(,),MaxRow,Rowsize,SortColumn)
' This sortfunction operates on a 2-dimensional numerical array
' Number of rows is <MaxRow> and number of columns is <RowSize>
' The variable <SortColumn> determines which column is sorted
DIM SwapRow(RowSize)
FOR isort=MaxRow TO 1 STEP -1
FOR jsort=2 TO isort
IF Array(jsort-1,SortColumn)>Array(jsort,SortColumn) THEN
' swap rows
FOR ci=1 TO RowSize
SwapRow(ci)=Array(jsort-1,ci) ' save lower row
Array(jsort-1,ci)=Array(jsort,ci) ' push to lower row
Array(jsort,ci) =SwapRow(ci) ' restore to upper row
NEXT ci
END IF
NEXT jsort
NEXT isort
END DEF ' BubbleSort
DEF Quicksort(Array(,),MaxRow,Rowsize,SortColumn)
' Non-recursive version of the QuickSort algorithm
' This sortfunction operates on a 2-dimensional numerical array
' Number of rows is <MaxRow> and number of columns is <RowSize>
' The variable <SortColumn> determines which column is sorted
ShowMaxStack=1 ' will display stack-usage if set to 1
MaxStackPtr=0
DIM SwapRow(RowSize), Stack1(30), Stack2(30)
StackPtr=0 ! HeadPtr=1 ! TailPtr=MaxRow
Qlabel2:
IF HeadPtr>TailPtr THEN
GOTO Qlabel4
ELSE
Pivot = Array((HeadPtr+TailPtr)/2,SortColumn)
qa=HeadPtr ! qb=TailPtr
Qlabel1:
IF Array(qa,SortColumn)<Pivot THEN ' while2
qa=qa+1
GOTO Qlabel1
END IF '1
Qlabel3:
IF Array(qb, SortColumn)>Pivot THEN
qb=qb-1
GOTO Qlabel3
END IF '2
IF qa<qb THEN
' swap rows
FOR qi=1 TO RowSize
SwapRow(qi)=Array(qa,qi)'save row qa
Array(qa,qi)=Array(qb,qi)'store row qb content in row qa
Array(qb,qi)=SwapRow(qi)'restore content of row qa to row qb
NEXT qi
qa=qa+1
qb=qb-1
GOTO Qlabel1
END IF '3
IF qa=qb THEN
qq = qb - 1
qr = qa + 1
ELSE
qq = qb
qr = qa
END IF '4
StackPtr = StackPtr + 1
IF MaxStackPtr<StackPtr THEN
MaxStackPtr=StackPtr
END IF '5
qp=HeadPtr
qs=TailPtr
IF (qq-qp)<(qs-qr) THEN
Stack1(StackPtr)=qr
Stack2(StackPtr)=qs
HeadPtr=qp
TailPtr=qq
ELSE
Stack1(StackPtr) = qp
Stack2(StackPtr) = qq
HeadPtr = qr
TailPtr = qs
END IF '6
GOTO Qlabel2
END IF '7
Qlabel4:
IF StackPtr > 0 THEN
HeadPtr = Stack1(StackPtr)
TailPtr = Stack2(StackPtr)
StackPtr = StackPtr - 1
GOTO Qlabel2
END IF '8
IF ShowMaxStack THEN
PRINT "Maximum stacksize=";MaxStackPtr
END IF '9
END DEF ' QuickSort
' =================== T E S T P R O G R A M ====================
RANDOMIZE
' -------------- Set switches for final time-testing
TimeTest=2 ' 1=BubbleSort, 2=QuickSort
TimeTestColumn=2 'this column (1,2 or 3) will be sorted in time-test
' Number of Columns is 3
' Columns: 1=index, 2=floating point, 3=integer
' ------------ Initiate arrays
ArraySize=10000 ' maximum number of 'rows', may be enlarged. Is size in time test.
RowCount=7 ' Number of 'rows' for comparative testing and demo
DIM Table(ArraySize,3)
GOTO TestTime ' skip columns-demo
Demo:
' ---------- fill Table with random numbers in columns 2 and 3
PRINT "Generating random data"
GOSUB FillTable
GOSUB ShowTable
PRINT
' ------------- give demo of both routines on two columns succesively
FOR method=1 TO 2
PRINT ">>> Sortmethod is:";
IF method=1 THEN
PRINT "BubbleSort"
ELSE
PRINT "QuickSort (non-recursive with stacks)"
END IF
PRINT
' ---------- sort
FOR TestColumn=2 TO 3
PRINT "Sorting data in column ";TestColumn
TableSort(Method,Table,Rowcount,TestColumn)
PRINT "Sort-time=";"#.###":Timer()/1000;" seconds."
GOSUB ShowTable
PRINT
NEXT TestColumn
WaitForEnter()
TEXT CLEAR
NEXT method
TestTime:
' ------------- Test on large array.
IF (TimeTest<>1) AND (TimeTest<>2) THEN
PRINT "STOPPED: The variable <TimeTest> should be 1 or 2"
PRINT "1 for BubbleSort, 2 for QuickSort"
END
ENDIF
RowCount=ArraySize
GOSUB FillTable
IF TimeTest=1 THEN
PRINT "Timing BubbleSort";
ELSE
PRINT "Timing QuickSort";
ENDIF
PRINT " on array of ";RowCount;" rows, sorting column";TimeTestColumn
TableSort(TimeTest,Table,Rowcount,TimeTestColumn)
PRINT "Sort-time=";"###.###":TIMER()/1000;" seconds."
IF ArraySize<=30 THEN GOSUB ShowTable
END
'========= PROGRAMSPECIFIC SUBROUTINES AND FUNCTIONS ================
DEF TableSort(Method,Table(,),Lines,Column)
TIME RESET
IF method=1 THEN
BubbleSort(Table,Lines,3,Column)
ELSE
QuickSort(Table,Lines,3,Column)
ENDIF
END DEF
FillTable: ' fill array with row-indices and random numbers
FOR n=1 TO RowCount
' PRINT ".";
Table(n,1)=n
Table(n,2)=10*RND(1)
Table(n,3)=100+RND(900)
NEXT n
RETURN
ShowTable:
PRINT "Index Random data"
FOR n=1 TO RowCount
PRINT "###": Table(n,1);" ";"#.####":Table(n,2);"######":Table(n,3)
NEXT n
RETURN
DEF WaitForEnter()
Msg$="Enter some character(s) to continue"
PRINT Msg$
INPUT Msg$:a$
END DEF