## quick sort

### Data

in lua

#### Tags

exchange sort, sorting

### Source Code

-- (In-place) Quicksort implementation
-- See : http://en.wikipedia.org/wiki/Quicksort#In-place_version

-- Partitions a portion of a list
local function partition(list, comp, left, right, pivot_index)
local pivot_value = list[pivot_index]
list[pivot_index], list[right] = list[right], list[pivot_index]
local store_index = left
for i = left, right-1 do
if comp(list[i], pivot_value) then
list[i], list[store_index] = list[store_index], list[i]
store_index = store_index + 1
end
end
list[store_index], list[right] = list[right], list[store_index]
return store_index
end

-- Performs in-place Quicksort
local function quicksort(list, comp, left, right)
left, right = left or 1, right or #list
if left < right then
local pivot_index = math.random(left, right)
local new_pivot_index = partition(list, comp, left, right, pivot_index)
quicksort(list, comp, left, new_pivot_index - 1)
quicksort(list, comp, new_pivot_index + 1, right)
end
return list
end

-- Quicksort function wrapper, to shadow access
-- to left and right bounds
-- list: a list to be ordered, in-place
-- comp: (optional) a comparison function
--  defaults to function(a, b) return a < b end
-- returns: the passed-in list, sorted
return function (list, comp)
comp = comp or function(a, b) return a < b end
return quicksort(list, comp)
end
-- Tests for quick_sort.lua
local quicksort = require 'quick_sort'

local total, pass = 0, 0

local function dec(str, len)
return #str < len
and str .. (('.'):rep(len-#str))
or str:sub(1,len)
end

local function run(message, f)
total = total + 1
local ok, err = pcall(f)
if ok then pass = pass + 1 end
local status = ok and 'PASSED' or 'FAILED'
print(('%02d. %68s: %s'):format(total, dec(message,68), status))
end

-- Comparison functions
local function le(a,b) return a <= b end
local function ge(a,b) return a >= b end

-- Checks if list is sorted
function is_sorted(list, comp)
comp = comp or le
for i = 2, #list do
if not comp(list[i-1],list[i]) then return false end
end
return true
end

-- Generates a table of n random values
local function gen(n)
local t = {}
for i = 1, n do t[i] = math.random(n) end
return t
end

math.randomseed(os.time())

run('Empty arrays', function()
local t = {}
assert(is_sorted(quicksort({})))
end)