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

                   j = nRight +1

                   DO WHILE j > i && as the pointers move toward each other without crossing

                             i=i+1

                             DO WHILE this.arData[i] < cKey && move the left pointer til we find one out of pos

                                      i=i+1

                             ENDDO

                             j=j-1

                             DO WHILE this.arData[j] > cKey && move the right pointer til we find one out of pos

                                      j=j-1

                             ENDDO

                             IF j > i

                                      this.Swap(j,i) && swap them

                             ENDIF

                   ENDDO

                   this.Swap(j,nLeft) && now we know the key goes into position nleft

                   this.QuickSort(nLeft, j-1) && sort left & right sides.

                   this.QuickSort(j+1, nRight)

          PROCEDURE SuperSort(nStart,nMax)

                   *What 14 lines of superfast code should go here to accomplish the task of sorting all the data?

ENDDEFINE

This is the VB version:

Public Class Form1

    Public arData(1) ' VB arrays are 0 to n-1

    Dim rand As Random = New Random()

    Dim nRows As Integer

    Dim nCols As Integer

    Dim nTotal As Integer

    Delegate Sub dlgSortFunc(ByVal nStart As Integer, ByVal nMax As Integer)

    Private Sub Form1_Load(ByVal sender As Object, ByVal e As System.EventArgs) Handles Me.Load

        Me.Font = New Font("Courier new", 10)

        Me.BackColor = Color.White

        Me.Width = 800

        Me.Height = 600

        Me.Text = "Sort demo b=Bubble, i=Insertion, s=Shell, q=Quick sorts r=reset"

    End Sub

    Sub SetUp()

        nRows = Me.Height / Font.Height - 3

        nCols = Me.Width / Font.Size - 2

        nTotal = nRows * nCols

        ReDim arData(nTotal - 1)

        Dim g As Graphics = Graphics.FromHwnd(Me.Handle)

        g.FillRectangle(Brushes.White, 0, 0, Me.Width, Me.Height)

        g.Dispose()

        Shuffle()

    End Sub

    Sub Shuffle()

        Dim i As Integer

        For i = 0 To nTotal - 1

            arData(i) = Chr(rand.Next(0, 26) + Asc("A"))

            ShowChar(arData(i), i)

        Next

    End Sub

    Sub ShowChar(ByVal s As String, ByVal nPos As Integer)

        Dim x, y As Integer

        Dim g As Graphics

        g = Graphics.FromHwnd(Me.Handle)

        x = Int((nPos Mod Me.nCols)) * Me.Font.Size

        y = Int((nPos / Me.nCols)) * Me.Font.Height

        g.FillRectangle(Brushes.White, x, y, Me.Font.Size, Me.Font.Height)

        g.DrawString(s, Me.Font, Brushes.Black, x, y)

        g.Dispose()

    End Sub

    Private Sub Form1_Paint(ByVal sender As Object, ByVal e As System.Windows.Forms.PaintEventArgs) Handles Me.Paint

        Dim g As Graphics = Graphics.FromHwnd(Me.Handle)

        g.FillRectangle(Brushes.White, 0, 0, Me.Width, Me.Height)

        g.Dispose()

        Me.SetUp()

    End Sub

    Private Sub Form1_KeyPress(ByVal sender As Object, ByVal e As System.Windows.Forms.KeyPressEventArgs) Handles Me.KeyPress

        If Asc(e.KeyChar) = 27 Then ' esc: end program

            End

        End If

        If e.KeyChar = "r" Then

            SetUp()

            Return

        End If

        Dim cSort As String = ""

        Dim nMax As Integer = Me.nTotal - 1

        Dim MyDlg As dlgSortFunc

        Select Case e.KeyChar

            Case "b" ' bubble sort

                cSort = "Bubble"

                nMax = Math.Min(nMax, 800)

                MyDlg = AddressOf Me.BubbleSort

            Case "i" ' insertion

                cSort = "Insertion"

                nMax = Math.Min(nMax, 800)

                MyDlg = AddressOf Me.InsertionSort

            Case "s"

                cSort = "Shell"

                MyDlg = AddressOf Me.ShellSort

            Case "q"

                cSort = "Quick"

                MyDlg = AddressOf Me.QuickSort

            Case "x"

                cSort = "Super"

                MyDlg = AddressOf Me.SuperSort

            Case Else

                MsgBox("Unknown command")

                Return

        End Select

        Me.Text = String.Format("{0} Sort # elements = {1}", cSort, nMax + 1)

        Dim nStart As Integer = My.Computer.Clock.TickCount

        MyDlg(0, nMax)

        Dim nEnd As Integer = My.Computer.Clock.TickCount - nStart

        Me.Text = String.Format("{0} Sort # elements = {1} Time={2:###.###}", cSort, nTotal, nEnd / 1000)

    End Sub

    Sub Swap(ByVal nPos1 As Integer, ByVal nPos2 As Integer)

        Dim cTemp

        cTemp = Me.arData(nPos1)

        Me.arData(nPos1) = Me.arData(nPos2)

        Me.arData(nPos2) = cTemp

        ShowChar(Me.arData(nPos1), nPos1)

        ShowChar(Me.ardata(nPos2), nPos2)

    End Sub

    Sub BubbleSort(ByVal nStart As Integer, ByVal nMax As Integer)

        Dim i, j As Integer

        For i = 0 To nMax

            For j = 0 To i

                If Me.arData(i) < Me.arData(j) Then

                    Swap(i, j)

                End If

         Next

        Next

    End Sub

    Sub InsertionSort(ByVal nStart As Integer, ByVal nMax As Integer)

        Dim i, j As Integer

        Dim t As Char

        For j = 1 To nMax

            If Me.arData(j - 1) > Me.arData(j) Then ' compare adjacent elements

                t = Me.arData(j)

                For i = j To 1 Step -1 ' shift the rest down

                    Me.arData(i) = Me.arData(i - 1)

                    Me.ShowChar(Me.arData(i), i)

                    If Me.arData(i - 1) < t Then

                        Exit For

                    End If

                Next

                Me.arData(i) = t

                Me.ShowChar(t, i)

            End If

        Next

    End Sub

    Sub ShellSort(ByVal nStart As Integer, ByVal nMax As Integer)

        Dim g, i, j As Integer

        g = Int(nMax / 2)

        Do While g > 0

            For i = g To nMax

                j = i - g

                Do While j >= 0 AndAlso Me.arData(j) > Me.arData(j + g)

                    Me.Swap(j, j + g)

                    j = j - g ' next group

                    If j < 0 Then

                        'Exit Do

                    End If

                Loop

            Next

            g = Int(g / 2)

        Loop

    End Sub

    Sub QuickSort(ByVal nLeft As Integer, ByVal nRight As Integer)

        Dim cKey As Char, i, j As Integer

        If nLeft >= nRight Then ' if the pointers cross, then we're done

            Return

        End If

        cKey = Me.arData(nLeft)

        i = nLeft ' start the left and right index pointers

        j = nRight + 1

        Do While j > i ' as the poitners move toward each other without crossing

            i = i + 1

            Do While Me.arData(i) < cKey 'move the left pointer til we find one out of pos

                i += 1

            Loop

            j -= 1

            Do While Me.arData(j) > cKey 'move the right pointer til we find one out of pos

                j -= 1

            Loop

            If j > i Then

            Me.Swap(j, i)

            End If

        Loop

        Me.Swap(j, nLeft) 'now we know the key goes into position nleft

        Me.QuickSort(nLeft, j - 1) ' sort left & right sides

        Me.QuickSort(j + 1, nRight)

    End Sub

    Sub SuperSort(ByVal nStart As Integer, ByVal nMax As Integer)

        'What 14 lines of superfast code should go here to accomplish the task of sorting all the data?

End Class