test/sort.lua

   1 $debug
   2
   3 function quicksort(a,r,s)
   4  if s<=r then return end
   5  local v, i, j = a[r], r, s+1
   6  repeat
   7   i=i+1; while a[i]<v do i=i+1 end
   8   j=j-1; while a[j]>v do j=j-1 end
   9   a[i],a[j]=a[j],a[i]
  10  until j<=i
  11  a[i],a[j]=a[j],a[i]                    -- undo last swap
  12  a[j],a[r]=a[r],a[j]
  13  quicksort(a,r,j-1)
  14  quicksort(a,j+1,s)
  15 end
  16
  17 function selectionsort(a,n)
  18  local i=1
  19  while i<=n do
  20   local m, j = i, i+1
  21   while j<=n do
  22    if a[j]>a[m] then m=j end            -- reverse sort
  23    j=j+1
  24   end
  25  a[i],a[m]=a[m],a[i]                    -- swap a[i] and a[m]
  26  i=i+1
  27  end
  28 end
  29
  30 function show(m,x)
  31  write(m,"\n\t")
  32  local i=0
  33  while x[i] do
  34   write(x[i])
  35   i=i+1
  36   if x[i] then write(",") end
  37  end
  38  write("\n")
  39 end
  40
  41 x={"Jan","Feb","Mar","Apr","May","Jun","Jul","Aug","Sep","Oct","Nov","Dec"}
  42
  43 n=1     while x[n] do n=n+1 end         -- count elements
  44 x[0]="A"        x[n]="Z"                -- quicksort need sentinels
  45
  46 show("original",x)
  47
  48 quicksort(x,1,n-1)
  49 show("after quicksort",x)
  50
  51 selectionsort(x, n-1)
  52 show("after reverse selection sort",x)