Microsoft Small Basic

Program Listing:
Embed this in your website
'sorting algorithm demo
'compares two O(n^2) algorithm (insertion sort)
'with n log^2 n algorithms (quick sort and shell sort)
'Zeven Provincien May 2010
'Modified by Jeremy Bupp Aug 2010

rows = 14
columns = 16
size = 24
offsetx = (columns+1) * size
offsety = (rows+1) * size
GraphicsWindow.Height=rows*size*2+size
Height = GraphicsWindow.Height
GraphicsWindow.Width=columns*size*2+size
Width = GraphicsWindow.Width
GraphicsWindow.Show()
GraphicsWindow.BackgroundColor = "SteelBlue"
GraphicsWindow.MouseDown = OnClick
continue = "false"

While (1=1)
  'set up random array
  For r = 0 To rows-1
    For c = 0 To columns-1
      red = Math.GetRandomNumber(256)-1
      green = Math.GetRandomNumber(256)-1
      blue = Math.GetRandomNumber(256)-1
      'red = 0
      green = 0 'comment this line and next to get a more colorful effect
      blue = 0
      GraphicsWindow.BrushColor = GraphicsWindow.GetColorFromRGB(red,green,blue)
      'GraphicsWindow.BrushColor = GraphicsWindow.GetRandomColor()
      i = r * columns + c
      boxes[i]["obj"] = Shapes.AddRectangle(size, size)
      boxes2[i]["obj"] = Shapes.AddRectangle(size,size)
      boxes3[i]["obj"] = Shapes.AddRectangle(size,size)
      Shapes.Move(boxes[i]["obj"], c * size, r * size)
      Shapes.Move(boxes2[i]["obj"],c * size + offsetx, r * size)
      Shapes.Move(boxes3[i]["obj"],c * size, r * size + offsety)
      boxes[i]["val"] = blue*256*256 + green*256 + red
      boxes2[i]["val"] = blue*256*256 + green*256 + red
      boxes3[i]["val"] = blue*256*256 + green*256 + red
    EndFor
  EndFor

  'set up for sorting
  arrlen = i

  GraphicsWindow.BrushColor = "black"
  title = "Sorting algorithm efficiency comparison"
  GraphicsWindow.DrawText(offsetx, offsety, title)
  arrsizetext = "Size of array = " + (arrlen + 1)
  GraphicsWindow.DrawText(offsetx, offsety+0.5*size, arrsizetext)

  GraphicsWindow.DrawText(offsetx, offsety+2*size, "Quick Sort:")
  start = Clock.ElapsedMilliseconds
  qSort()
  bubtime = Clock.ElapsedMilliseconds - start
  bubtext = "Elapsed time = " + bubtime/1000 + " seconds"
  GraphicsWindow.DrawText(offsetx+100, offsety+2*size, bubtext)

  GraphicsWindow.DrawText(offsetx, offsety+3*size, "Insertion Sort:")
  start = Clock.ElapsedMilliseconds
  insertionsort()
  instime = Clock.ElapsedMilliseconds - start
  instext = "Elapsed time = " + instime/1000 + " seconds"
  GraphicsWindow.DrawText(offsetx+100, offsety+3*size, instext)

  GraphicsWindow.DrawText(offsetx, offsety+4*size, "Shell Sort:")
  start = Clock.ElapsedMilliseconds
  shellsort()
  shelltime = Clock.ElapsedMilliseconds - start
  shelltext = "Elapsed time = " + shelltime/1000 + " seconds"
  GraphicsWindow.DrawText(offsetx+100, offsety+4*size, shelltext)

  GraphicsWindow.DrawText(offsetx, offsety+6*size, "Program ended.")
  While continue <> "true"
  endwhile
  GraphicsWindow.BrushColor = "SteelBlue"
  GraphicsWindow.FillRectangle(offsetx, offsety, Width - offsetx, Height - offsety)
  continue = "false"
endwhile

Sub OnClick
  continue = "true"
endsub

Sub shellsort
  inc = Math.Round(arrlen/2)
  While inc > 0
    For i = inc To arrlen
      temp = boxes3[i]["val"]
      tempbox = boxes3[i]["obj"]
      j = i
      while (j >= inc) and (boxes3[j-inc]["val"] > temp)
        boxes3[j]["val"] = boxes3[j-inc]["val"]
        boxes3[j]["obj"] = boxes3[j-inc]["obj"]
        r = Math.Floor((j)/columns)
        c = Math.Remainder(j,columns)
        Shapes.Move(boxes3[j]["obj"],c * size, r * size + offsety)
        j = j - inc
      EndWhile
      boxes3[j]["val"] = temp
      boxes3[j]["obj"] = tempbox
      r = Math.Floor((j)/columns)
      c = Math.Remainder(j,columns)
      Shapes.Move(boxes3[j]["obj"],c * size, r * size + offsety)
    EndFor
    inc = Math.Round(inc/2.2)
  Endwhile

Endsub

Sub insertionsort

  For i = 1 to arrlen
    value = boxes2[i]["val"]
    boxtemp = boxes2[i]["obj"]
    j = i - 1
    done = "false"
    While done = "false"
      If boxes2[j]["val"] > value then
        boxes2[j + 1]["val"] = boxes2[j]["val"]
        boxes2[j+1]["obj"] = boxes2[j]["obj"]
        r = Math.Floor((j+1)/columns)
        c = Math.Remainder(j+1,columns)
        Shapes.Move(boxes2[j+1]["obj"],c * size + offsetx, r * size)
        j = j - 1
        If j < 0 then
          done = "true"
        EndIf
      Else
        done = "true"
      EndIf
      'Program.Delay(10)
    EndWhile
    boxes2[j+1]["val"] = value
    boxes2[j+1]["obj"] = boxtemp
    r = Math.Floor((j+1)/columns)
    c = Math.Remainder(j+1,columns)
    Shapes.Move(boxes2[j+1]["obj"],c * size + offsetx, r * size)
  EndFor

Endsub

Sub bubblesort
  imax = arrlen
  'highval = boxes[1]["val"]
  swapped = "true"
  While swapped = "true"
    swapped = "false"
    For bubi = 1 To imax
      If boxes[bubi]["val"] < boxes[bubi-1]["val"] Then
        swap()
      EndIf
      'Program.Delay(10)
    Endfor
    imax = imax - 1
  Endwhile
EndSub

sub qSort
  val = "val"
  obj = "obj"
  lowInd = 1
  highInd = 2
  i[lowInd] = 0
  i[highInd] = arrlen
  Input = 1
  Larger = 2
  Eq = 3
  Stack.PushValue(Input, i)
  While Stack.GetCount(Input) > 0
    i = Stack.PopValue(Input)
    'TextWindow.WriteLine("i = " + i)
    'ans = TextWindow.Read()
    'If ans <> "" Then
    ' For ggg = i[lowInd] To i[highInd]
    ' TextWindow.WriteLine(ggg + " = " + boxes[ggg][val])
    'EndFor
    'EndIf

    If (i[lowInd] < i[highInd]) Then
      ' mid = Math.GetRandomNumber(i[highInd] - i[lowInd]) + i[lowInd]
      Pivot = boxes[i[lowInd]][val]
      For ind = i[lowInd] To i[highInd]
        If boxes[ind][val] > Pivot then
          Stack.PushValue(Larger, ind)
        ElseIf boxes[ind][val] = Pivot then
          Stack.PushValue(Eq, ind)
        EndIf
      endfor
      If Stack.GetCount(Larger) = 0 then
        tl= larger
        Larger  = Eq
        Eq = tl
        t = 1
      Else
        t = 0
      endif
      hi= i[highInd]
      While Stack.GetCount(Larger) > 0
        li = Stack.PopValue(Larger)
        If (li < hi) Then
          temp = boxes[li][val]
          boxes[li][val] = boxes[hi][val]
          boxes[hi][val] = temp

          temp = boxes[li][obj]
          boxes[li][obj] = boxes[hi][obj]
          boxes[hi][obj] = temp

          r = Math.Floor((li)/columns)
          c = Math.Remainder(li,columns)
          Shapes.Move(boxes[li]["obj"],c * size, r * size)

          r = Math.Floor((hi)/columns)
          c = Math.Remainder(hi,columns)
          Shapes.Move(boxes[hi]["obj"],c * size, r * size)
        EndIf
        hi = hi - 1
      EndWhile
      r[lowInd] = i[lowInd]
      r[highInd] = hi
      Stack.PushValue(Input, r)

      If t = 0 then
        r[lowInd] = hi + 1
        r[highInd] = i[highInd]
        Stack.PushValue(Input, r)
      endif

      While Stack.GetCount(Eq) > 0
        Stack.PopValue(Eq)
      EndWhile
    EndIf
  endwhile
endsub


Sub swap

  boxtemp = boxes[bubi-1]["obj"]
  boxtempval = boxes[bubi-1]["val"]
  boxes[bubi-1]["obj"]=boxes[bubi]["obj"]
  boxes[bubi-1]["val"]=boxes[bubi]["val"]
  boxes[bubi]["obj"]=boxtemp
  boxes[bubi]["val"]=boxtempval
  'highval=boxes[i]["val"]
  r = Math.Floor((bubi-1)/columns)
  c = Math.Remainder(bubi-1,columns)
  Shapes.Move(boxes[bubi-1]["obj"],c * size, r * size)
  r = Math.Floor((bubi)/columns)
  c = Math.Remainder(bubi,columns)
  Shapes.Move(boxes[bubi]["obj"],c * size, r * size)
  swapped = "true"

Endsub

Copyright (c) Microsoft Corporation. All rights reserved.