1 
 two implementations of a sort function 

2 
 this is an example only. Lua has now a builtin function "sort" 

3 


4 
 extracted from Programming Pearls, page 110 

5 
function qsort(x,l,u,f) 

6 
if l<u then 

7 
local m=math.random(u(l1))+l1  choose a random pivot in range l..u 

8 
x[l],x[m]=x[m],x[l]  swap pivot to first position 

9 
local t=x[l]  pivot value 

10 
m=l 

11 
local i=l+1 

12 
while i<=u do 

13 
 invariant: x[l+1..m] < t <= x[m+1..i1] 

14 
if f(x[i],t) then 

15 
m=m+1 

16 
x[m],x[i]=x[i],x[m]  swap x[i] and x[m] 

17 
end 

18 
i=i+1 

19 
end 

20 
x[l],x[m]=x[m],x[l]  swap pivot to a valid place 

21 
 x[l+1..m1] < x[m] <= x[m+1..u] 

22 
qsort(x,l,m1,f) 

23 
qsort(x,m+1,u,f) 

24 
end 

25 
end 

26 


27 
function selectionsort(x,n,f) 

28 
local i=1 

29 
while i<=n do 

30 
local m,j=i,i+1 

31 
while j<=n do 

32 
if f(x[j],x[m]) then m=j end 

33 
j=j+1 

34 
end 

35 
x[i],x[m]=x[m],x[i]  swap x[i] and x[m] 

36 
i=i+1 

37 
end 

38 
end 

39 


40 
function show(m,x) 

41 
io.write(m,"\n\t") 

42 
local i=1 

43 
while x[i] do 

44 
io.write(x[i]) 

45 
i=i+1 

46 
if x[i] then io.write(",") end 

47 
end 

48 
io.write("\n") 

49 
end 

50 


51 
function testsorts(x) 

52 
local n=1 

53 
while x[n] do n=n+1 end; n=n1  count elements 

54 
show("original",x) 

55 
qsort(x,1,n,function (x,y) return x<y end) 

56 
show("after quicksort",x) 

57 
selectionsort(x,n,function (x,y) return x>y end) 

58 
show("after reverse selection sort",x) 

59 
qsort(x,1,n,function (x,y) return x<y end) 

60 
show("after quicksort again",x) 

61 
end 

62 


63 
 array to be sorted 

64 
x={"Jan","Feb","Mar","Apr","May","Jun","Jul","Aug","Sep","Oct","Nov","Dec"} 

65 


66 
testsorts(x) 
