Visual Sorting Algorithm comparison
When I bought my first IBM PC around 1981, I wrote a program to demonstrate the speed of various sorting algorithms. It filled the screen with random characters, then the user could choose amongst a few sorting techniques and watch the sort algorithm in action as the data moved around on the screen. Watching the data move helps to see how the algorithm works.
The program could access the graphics card directly, writing characters directly into the video memory. For Foxpro, I used the @..SAY command to put a string at a particular row and column. For VB I used the Graphics.DrawString method.
Below are a Fox and VB reimplementation of this demo.
Run the code and type “B” for Bubble Sort, i=Insertion Sort, s=Shell Sort, q=Quick Sort. R will reset the data to be random.
Which one is fastest for you?
Some of the sorts take a *long* time so just the first few elements are sorted.
I’ve removed the Supersort code as an exercise for the reader: what 14 lines of code will achieve the result *much* faster than any other sorting algorithm?
Hint: none of the other algorithms require much additional storage other than a few local variables. The SuperSort uses an array of size 26.
CLEAR
PUBLIC ox
ox= NEWOBJECT("SortForm")
DEFINE CLASS SortForm AS Form
left=200
width=800
height=600
nRows=0
nCols=0
FontName="Courier New"
FontSize=10
BackColor=0xffffff
DIMENSION arData[1]
nTotal=0
PROCEDURE init
* RAND(SECONDS()) && randomize generator
this.show
this.Setup
PROCEDURE Setup
this.nRows=INT(this.height/FONTMETRIC(1)-1)
this.nCols=INT(this.width/FONTMETRIC(6))
this.nTotal= this.nRows*this.nCols
DIMENSION this.arData[this.nTotal]
this.Shuffle
PROCEDURE Shuffle
FOR i = 1 TO this.nTotal
this.arData[i]=CHR(RAND()*26+ASC('A'))
@ INT((i-1)/this.nCols), INT((i-1)%this.nCols) say this.arData[i]
ENDFOR
this.Caption="# elements = "+TRANSFORM(thisform.nTotal)+" Try Bubble, Insertion, Shell, Quick sorts"
PROCEDURE Resize
this.Cls
this.Setup
PROCEDURE KeyPress(nKeyCode, nShiftAltCtrl)
IF nKeyCode=27 && <escape> Exit program
thisform.Release
RETURN
ENDIF
IF nKeyCode=ASC("r") && reset random data
thisform.Setup
RETURN
ENDIF
cSort=""
nMax=thisform.nTotal
DO CASE
CASE nKeyCode=ASC("b") && Bubble
cSort="Bubble"
nMax=MIN(thisform.nTotal,1000) && slow sort: limit # of items
CASE nKeyCode=ASC("i") && Insertion
cSort="Insertion"
nMax=MIN(thisform.nTotal,1000) && slow sort: limit # of items
CASE nKeyCode=ASC("s") && Shell Sort
cSort="Shell"
CASE nKeyCode=ASC("q") && Quick Sort
cSort="Quick"
CASE nKeyCode=ASC("x") &&Super Sort
cSort="Super"
OTHERWISE
MESSAGEBOX("Unknown command")
RETURN
ENDCASE
this.Caption="# elements = "+TRANSFORM(nMax)+" Starting "+cSort+" Sort"
nStart = SECONDS()
this.&cSort.Sort(1,nMax) && Call the sort routine
this.Caption="# elements = "+TRANSFORM(thisform.nTotal)+" "+cSort+ " "+TRANSFORM(SECONDS()-nStart,"999.999")
PROCEDURE Swap(nPos1,nPos2) && Exchange the positions of 2 elements
LOCAL cTemp
cTemp=this.arData[nPos1]
this.arData[nPos1]=this.arData[nPos2]
this.arData[nPos2]= cTemp
@ INT((nPos1-1)/this.nCols), INT((nPos1-1)%this.nCols) say this.arData[nPos1]
@ INT((nPos2-1)/this.nCols), INT((nPos2-1)%this.nCols) say this.arData[nPos2]
PROCEDURE BubbleSort(nStart,nMax)
LOCAL i,j
FOR i = 1 TO nMax && loop through all elements
FOR j= 1 TO i && loop through current pos
IF this.arData[i] < this.arData[j]
this.Swap(i,j)
ENDIF
ENDFOR
ENDFOR
PROCEDURE InsertionSort(nStart,nMax)
LOCAL i, j,t
FOR j = 2 TO nMax
IF this.arData[j-1] > this.arData[j] && compare adjacent elements
t = this.arData[j]
FOR i = j TO 2 STEP -1 && make room by moving the rest down
this.arData[i]=this.arData[i-1]
@ INT((i-1)/this.nCols), INT((i-1)%this.nCols) say this.arData[i-1]
IF this.arData[i-1] <= t
EXIT
ENDIF
ENDFOR
this.arData[i]=t
@ INT((i-1)/this.nCols), INT((i-1)%this.nCols) say t
ENDIF
ENDFOR
PROCEDURE ShellSort(nStart,nMax)
LOCAL g,i,j
g = INT(nMax/2)
DO WHILE g > 0 && g is successively half of nMax
FOR i = g+1 TO nMax
j = i - g
DO WHILE j>0 AND this.arData[j] > this.arData[j+g] && do we swap?
this.Swap(j,j+g)
j=j-g && next group
ENDDO
ENDFOR
g=INT(g/2)
ENDDO
PROCEDURE QuickSort(nLeft,nRight) && left and right pointers into data. Divide and conquer
LOCAL cKey,i,j
IF nLeft >= nRight && if the pointers cross, then we're done
RETURN
ENDIF
cKey = this.arData[nLeft] && the key is the first element
i=nLeft && start the left and right pointers