Lua 3.13.1

1 files changed, 40 insertions, 29 deletions

diff --git a/test/sort.lua b/test/sort.lua
index a5eb0956..41473f4a 100644
--- a/test/sort.lua
+++ b/test/sort.lua
@@ -1,35 +1,42 @@
-$debug
-
-function quicksort(a,r,s)
- if s<=r then return end
- local v, i, j = a[r], r, s+1
- repeat
-  i=i+1; while a[i]<v do i=i+1 end
-  j=j-1; while a[j]>v do j=j-1 end
-  a[i],a[j]=a[j],a[i]
- until j<=i
- a[i],a[j]=a[j],a[i]			-- undo last swap
- a[j],a[r]=a[r],a[j]
- quicksort(a,r,j-1)
- quicksort(a,j+1,s)
+-- extracted from Programming Pearls, page 110
+function qsort(x,l,u,f)
+ if l<u then
+  local m=random(u-(l-1))+l-1		-- choose a random pivot in range l..u
+  x[l],x[m]=x[m],x[l]			-- swap pivot to first position
+  local t=x[l]				-- pivot value
+  m=l
+  local i=l+1
+  while i<=u do
+    -- invariant: x[l+1..m] < t <= x[m+1..i-1]
+    if f(x[i],t) then
+      m=m+1
+      x[m],x[i]=x[i],x[m]		-- swap x[i] and x[m]
+    end
+    i=i+1
+  end
+  x[l],x[m]=x[m],x[l]			-- swap pivot to a valid place
+  -- x[l+1..m-1] < x[m] <= x[m+1..u]
+  qsort(x,l,m-1,f)
+  qsort(x,m+1,u,f)
+ end
 end
 
-function selectionsort(a,n)
+function selectionsort(x,n,f)
  local i=1
  while i<=n do
-  local m, j = i, i+1
+  local m,j=i,i+1
   while j<=n do
-   if a[j]>a[m] then m=j end		-- reverse sort
+   if f(x[j],x[m]) then m=j end
    j=j+1
   end
- a[i],a[m]=a[m],a[i]			-- swap a[i] and a[m]
+ x[i],x[m]=x[m],x[i]			-- swap x[i] and x[m]
  i=i+1
  end
 end
 
 function show(m,x)
  write(m,"\n\t")
- local i=0
+ local i=1
  while x[i] do
   write(x[i])
   i=i+1
@@ -38,15 +45,19 @@ function show(m,x)
  write("\n")
 end
 
-x={"Jan","Feb","Mar","Apr","May","Jun","Jul","Aug","Sep","Oct","Nov","Dec"}
-
-n=1	while x[n] do n=n+1 end		-- count elements
-x[0]="A"	x[n]="Z"		-- quicksort need sentinels
-
-show("original",x)
+function testsorts(x)
+ local n=1
+ while x[n] do n=n+1 end; n=n-1		-- count elements
+ show("original",x)
+ qsort(x,1,n,function (x,y) return x<y end)
+ show("after quicksort",x)
+ selectionsort(x,n,function (x,y) return x>y end)
+ show("after reverse selection sort",x)
+ qsort(x,1,n,function (x,y) return x<y end)
+ show("after quicksort again",x)
+end
 
-quicksort(x,1,n-1)
-show("after quicksort",x)
+-- array t be sorted
+x={"Jan","Feb","Mar","Apr","May","Jun","Jul","Aug","Sep","Oct","Nov","Dec"}
 
-selectionsort(x, n-1)
-show("after reverse selection sort",x)
+testsorts(x)