-- somente separa os grupos 
-- menores a esquerda
-- maiores a direita
-- 
function separa(e,d)

	-- pivot eh o ultimo elemento
	local pivot = v[d]

	-- incrementado quando test eh verdadeiro
	-- candidato a troca 
	local j = e

	-- testa do inicio ateh antes do pivot
	for k=e, d-1 do
	
		-- se elemento de teste for menor ou igual ao pivot
		-- troca o elemento v[j] com o elemento testado
		if v[k] <= pivot then

			local temp = v[j]
			v[j] = v[k]
			v[k] = temp
			j = j +1
		end
	
	end

	v[d] = v[j]
	v[j] = pivot
	return j	

end

function quicksort(e,d)

	if e < d then
		meio = separa(e,d)
		
		-- o meio nao participa da proxima recursao !
		quicksort(e,meio-1)
		quicksort(meio+1,d)
	end

end

	v = { 9, 6, 3, 5, 2, 7, 10, 12, 1 }
	N = table.getn(v)
	
	print( table.concat(v,",") ) 
	quicksort(1, N)
	print( table.concat(v,",") )