Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Luaでソートアルゴリズムで遊んだやつ
--Sort Algorithm Test
--コマンドライン引数
--[数列の個数] [最大値] [最小値] [-s] [-b]
-- [-s] [-b] でそれぞれのソートを無効化
s = false
b = false
function print_(str)
if s then return end
print(str)
end
function arrayCopy(array)
local result = {}
for i,v in ipairs(array) do
result[i] = array[i]
end
return result
end
function arrayPrint(array)
if s then return end
io.write("Array {")
for i,v in ipairs(array) do
io.write(string.format("%d",v))
if i~=#array then
io.write(",")
else
io.write("}\n")
end
end
end
function bubbleSort(array)
for i=1,#array-1 do
local j = #array
while j>=i+1 do
if(array[j] < array[j-1]) then
local x = array[j-1]
array[j-1] = array[j]
array[j] = x
end
j = j - 1
end
end
return array
end
function quickSort(list)
local result = {}
local num = false
local function sort (array)
--5以下はバブルで
if #array < 10 or num then
if not(num) then
local res = bubbleSort(array)
for i=1,#res do
result[#result+1] = res[i]
end
else
for i=1,#array do
result[#result+1] = array[1]
end
end
num=false
return
end
--[[--3つ選び中央値を得る
local max,cen,min
local ca ={}
ca[1] = array[math.random(#array)]
--[[ca[2] = array[math.random(#array)]
ca[3] = array[math.random(#array)]
ca[4] = array[math.random(#array)]
ca[5] = array[math.random(#array)]
ca[6] = array[math.random(#array)]
ca[7] = array[math.random(#array)]
ca[8] = array[math.random(#array)]
for i=1,#ca do
if max==nil or max < ca[i] then
max=ca[i]
end
if min==nil or min > ca[i] then
min=ca[i]
end
if ca[i]==max or ca[i]==min then
cen = max
end
end
if cen==nil then
for i=1,#ca do
if ca[i]~=min and ca[i]~=max then
cen=ca[i]
end
end
end]]--
--cenがピボットに.
local cen = array[math.random(#array)]
local lows = {}
local highs = {}
local cnt = 0
for i=1,#array do
if array[i]>=cen then highs[#highs+1]=array[i] end
if array[i]<cen then lows[#lows+1]=array[i] end
if array[i]==array[1] then
cnt = cnt + 1
end
end
if cnt==#array then num=true end
if #lows > 0 then sort(lows) end
if #highs > 0 then sort(highs) end
return
end
sort(list)
return result
end
function main()
local len
if type(arg[1])=="nil" then
len = 100
else
len = math.abs(arg[1])
end
local max
if type(arg[2])=="nil" then
max = 100
else
max = arg[2]
end
local min
if type(arg[3])=="nil" then
min = 0
else
min = arg[3]
end
if arg[4]=="-s" then
s = true
end
if arg[5]=="-b" then
b = true
end
math.randomseed(os.time());
local array = {}
for i=1,len do
array[i] = math.random(min,max)
end
arrayPrint(array)
print("Array created..")
local ts,te
local result
local temp = arrayCopy(array)
print("\nquick sort...");
ts = os.time()
result = quickSort(temp)
te = os.time()
arrayPrint(result)
print(string.format("%d seconds done...",os.difftime(te,ts)))
print("")
if not(b) then
temp = arrayCopy(array)
print("\nbubble sort...");
ts = os.time()
result = bubbleSort(temp)
te = os.time()
arrayPrint(result)
print(string.format("%d seconds done...",os.difftime(te,ts)))
print("")
end
temp = arrayCopy(array)
print("\nLua table.sort()...");
ts = os.time()
table.sort(temp)
te = os.time()
arrayPrint(temp)
print(string.format("%d seconds done...",os.difftime(te,ts)))
print("")
end
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment