test/sort/q.lua

   1 function quicksort(r,s)
   2         if s<=r then return end         -- caso basico da recursao
   3         local v=x[r]
   4         local i=r
   5         local j=s+1
   6         repeat
   7                 repeat i=i+1 until x[i]>=v
   8                 repeat j=j-1 until x[j]<=v
   9                 x[i],x[j]=x[j],x[i]
  10         until j<=i                      -- separacao
  11         x[i],x[j]=x[j],x[i]             -- undo last swap
  12         x[j],x[r]=x[r],x[j]
  13         quicksort(r,j-1)                -- recursao
  14         quicksort(j+1,s)
  15 end
  16
  17 function main()
  18  x=@()
  19  n=-1
  20  n=n+1; x[n]="a"
  21  n=n+1; x[n]="waldemar"
  22  n=n+1; x[n]="luiz"
  23  n=n+1; x[n]="lula"
  24  n=n+1; x[n]="peter"
  25  n=n+1; x[n]="raquel"
  26  n=n+1; x[n]="camilo"
  27  n=n+1; x[n]="andre"
  28  n=n+1; x[n]="marcelo"
  29  n=n+1; x[n]="sedrez"
  30  n=n+1; x[n]="z"
  31 -- sort(x,n)
  32  quicksort(1,n-1)
  33 print(x[0]..","..x[1]..","..x[2]..","..x[3]..","..x[4]..","..x[5]..","..x[6]..","..x[7]..","..x[8]..","..x[9]..","..x[10])
  34 end
  35
  36 function sort(a,n)                      -- selection sort
  37  local i=1
  38  while i<=n do
  39   local m=i
  40   local j=i+1
  41   while j<=n do
  42    if a[j]<a[m] then m=j end
  43    j=j+1
  44   end
  45  a[i],a[m]=a[m],a[i]                    -- swap a[i] and a[m]
  46  print (i, a[i])
  47  i=i+1
  48  end
  49 end
  50
  51 main()