Help with error in my quickSort function.

Hello,
I'm trying to write a simple quick sort function for lua. I keep getting a weird error though when I execute the function. First I'll show ou my function then I'll explain.

function quickSort(sortTable)
    local lower, higher, pivot, pivotValue = {}, {}, 1, tonumber(sortTable[pivot])

    if (#sortTable <= 1) then
        return sortTable
    end

    for i = 1, #sortTable do
        if (tonumber(sortTable[i]) > pivotValue) then -- error occurs here
            table.insert(higher, sortTable[i])
        else
            table.insert(lower, sortTable[i])
        end
    end

    return quickSort(lower), quickSort(higher)
end

When I run this code with a table that only contains numbers (example: {1,4,2,6,9}) which is what I wrote this to sort, I get the error

programName:lineWhereErrorOccurs: attempt to compare nil with number

.
I don't have a clue which one is nil nor why it is even throwing that error in the first place because all table positions should be numbers. When I ran this on my "real" lua interpreter the call traceback showed that the error occurs on the first iteration of quickSort(). Is there anything I'm missing here? or is this just my bad luck?

well believe it or not the problem is actually here

local lower, higher, pivot, pivotValue = {}, {}, 1, tonumber(sortTable[pivot])

and it is because pivot is not yet defined when you're trying to set pivotValue.
the fix would be to do this

local lower, higher, pivot, pivotValue = {}, {}, 1, tonumber(sortTable[1])

however you will also get another problem which is a stack overflow, why? well because you're calling quicksort again with each of your result tables. What is the purpose of the low and high exactly?

it seems that __lt switches the values, which is why it was saying that there was a nil value in the table, instead of quicksort being nil. I'd assume this is a bug in LuaJ.

I'm assuming you're just wanting say the example {1,4,2,9,6} to output as {1,2,4,6,9}, am I correct in this assumption?

I do want output to be {1,2,4,6,9}. This is an attempt to translate the python example of quick sort that I found

def quickSort(arr):
    less = []
    pivotList = []
    more = []
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        for i in arr:
            if i < pivot:
                less.append(i)
            elif i > pivot:
                more.append(i)
            else:
                pivotList.append(i)
        less = quickSort(less)
        more = quickSort(more)
        return less + pivotList + more

So what I want it to do is choose a pivot, then separate the table into two tables, a table with values less than the pivot's value and one with values greater than the pivot's value. The function will then recursively call itself, each time splitting it's input into two, until the table it is called with is only one long (which is inherently sorted) those then return up the chain and the original call will return the sorted table. I tried an in-place (which would use way less memory) version as well but abandoned it since I kept having problems there too (it seems like it is running io.read() {it freezes execution, while allowing me to type stuff in}). That code follows (note that this was created trying to replicate this tutorial)

function quickSort(sortTable, sortStart, sortEnd)
	sortStart, sortEnd = sortStart or 1, sortEnd or #sortTable
	if (sortEnd - sortStart < 1) then
		return sortTable
	end

	math.randomseed(os.time())
	local pivot = math.floor(math.random(sortStart, sortEnd))

	local scratch = sortTable[sortEnd] -- swap sortEnd and pivot
	sortTable[sortEnd] = sortTable[pivot]
	sortTable[pivot] = scratch

	-- pivot is now sortEnd

	local placeI, placeJ = sortStart, sortEnd - 1
	while true do -- (while placeI < placeJ)
		placeI, placeJ = sortStart, sortEnd - 1
		while (sortTable[placeI] < sortTable[sortEnd]) do
			placeI = placeI + 1
		end
		while (sortTable[placeJ] > sortTable[sortEnd]) do
			placeJ = placeJ - 1
		end
		if (placeI > placeJ) then
			break
		else
			-- swap placeI and placeJ
			scratch = sortTable[placeJ]
			sortTable[placeJ] = sortTable[placeI]
			sortTable[placeI] = scratch
		end
	end

	scratch = sortTable[placeI] -- swap placeI and pivot (placeI should be < pivot)
	sortTable[placeI] = sortTable[sortEnd]
	sortTable[sortEnd] = scratch

	sortTable = quickSort(sortTable, sortStart, placeJ - 1)
	return quickSort(sortTable, placeJ + 1, sortEnd)
end

Ahh ok makes sense what you're doing. However there is already a function built into Lua, I suggest you just use that. :)/> table.sort.

I can never get that to work :P/> can I just do

sortedTable = table.sort(unsortedTable)

or do I have to have more there?
because I always get the result of sortedTable being nil. When I run the above code.

table.sort doesn't return anything, it sorts the table that was passed in. Just do table.sort(myTable), and myTable will now be sorted :)/>. :)/>

That helps immensely, thanks! So to achieve the same goal as above I should do:

sortedTable = unsortedTable
table.sort(sortedTable)

?

Is there any reason why it might be "freezing" like it is? Also after making edits to my function in my op it does the same thing and "freezes" too.

function myQuickSort(sortTable)
	local lower, higher, pivot = {}, {}, 1
	pivotValue = tonumber(sortTable[pivot])

	if (#sortTable <= 1) then
		return sortTable
	end

	for i = 1, #sortTable do
		if (tonumber(sortTable[i]) > pivotValue) then
			table.insert(higher, sortTable[i])
		else
			table.insert(lower, sortTable[i])
		end
	end

	return myQuickSort(lower), myQuickSort(higher)
end

EDIT: Never mind, I let it run rather than just terminating it and eventually the program crashed citing Stack Overflow (just like theoriginalbit predicted) even on my laptop and not in CC

How does this not cause a stack overflow? Its also calling itself twice

function quicksort(sortTable, sortStart, sortEnd)
	sortStart, sortEnd = sortStart or 1, sortEnd or #sortTable
	--partition w.r.t. first element
	if(sortEnd - sortStart < 1) then return sortTable end
	local pivot = sortStart
	for i = sortStart + 1, sortEnd do
		if sortTable[i] <= sortTable[pivot] then
			local temp = sortTable[pivot + 1]
			sortTable[pivot + 1] = sortTable[pivot]
			if(i == pivot + 1) then
				sortTable[pivot] = temp
			else
				sortTable[pivot] = sortTable[i]
				sortTable[i] = temp
			end
			pivot = pivot + 1
		end
	end
	sortTable = quicksort(sortTable, sortStart, pivot - 1)
	return quicksort(sortTable, pivot + 1, sortEnd)
end

edit: I found this here by the way.

happydude11209, on 07 June 2013 - 02:46 PM said:

That helps immensely, thanks! So to achieve the same goal as above I should do:

sortedTable = unsortedTable
table.sort(sortedTable)

Nope, this would change the sortedTable and the unsortedTable too, tables are a reference, not a value, so simply doing = means that both variables contain the same pointer, so when you change one, it changes the other too as you're changing the data in memory. So what you need to do is take a copy of the table, something like this

sortedTable = {}
--# iterate through each element in the table
for k,v in pairs(unsortedTable) do
  sortedTable[k] = v
end

happydude11209, on 07 June 2013 - 02:49 PM said:

Is there any reason why it might be "freezing" like it is? Also after making edits to my function in my op it does the same thing and "freezes" too.

EDIT: Never mind, I let it run rather than just terminating it and eventually the program crashed citing Stack Overflow (just like theoriginalbit predicted) even on my laptop and not in CC

Chances are it is freezing because it is a big table, I'm surprised you didn't actually get a "too long without yielding" instead of the stack overflow. btw the stack size is 256, no matter what machine you're on.


oh just a side note also here would be a solution that sorts a table in Lua (does not preserve the existing table)

function sort( data )
  for i = 1, #data do
	for j = 1, #data - 1 do
	  if data[j] > data[j + 1] then
		data[j], data[j+1] = data[j+1], data[j] --# swap the values
	  end
	end
  end
end

here is one that would preserve the existing table and return a new one

function sort( data )
  --# copy the table
  local ret = {}
  for i,v in ipairs(data) do
	ret[i] = v
  end
  --# sort the new table
  for i = 1, #ret do
	for j = 1, #ret - 1 do
	  if ret[j] > ret[j + 1] then
		ret[j], ret[j + 1] = ret[j + 1], ret[j] --# swap the values
	  end
	end
  end
  --# return our new table
  return ret
end

theoriginalbit, on 07 June 2013 - 03:02 PM said:

happydude11209, on 07 June 2013 - 02:46 PM said:

That helps immensely, thanks! So to achieve the same goal as above I should do:

sortedTable = unsortedTable
table.sort(sortedTable)

Nope, this would change the sortedTable and the unsortedTable too, tables are a reference, not a value, so simply doing = means that both variables contain the same pointer, so when you change one, it changes the other too as you're changing the data in memory. So what you need to do is take a copy of the table, something like this

sortedTable = {}
--# iterate through each element in the table
for k,v in pairs(unsortedTable) do
  sortedTable[k] = v
end

happydude11209, on 07 June 2013 - 02:49 PM said:

Is there any reason why it might be "freezing" like it is? Also after making edits to my function in my op it does the same thing and "freezes" too.

EDIT: Never mind, I let it run rather than just terminating it and eventually the program crashed citing Stack Overflow (just like theoriginalbit predicted) even on my laptop and not in CC

Chances are it is freezing because it is a big table, I'm surprised you didn't actually get a "too long without yielding" instead of the stack overflow. btw the stack size is 256, no matter what machine you're on.


oh just a side note also here would be a solution that sorts a table in Lua (does not preserve the existing table)

function sort( data )
  for i = 1, #data do
	for j = 1, #data - 1 do
	  if data[j] > data[j + 1] then
		data[j], data[j+1] = data[j+1], data[j] --# swap the values
	  end
	end
  end
end

here is one that would preserve the existing table and return a new one

function sort( data )
  --# copy the table
  local ret = {}
  for i,v in ipairs(data) do
	ret[i] = v
  end
  --# sort the new table
  for i = 1, #ret do
	for j = 1, #ret - 1 do
	  if ret[j] > ret[j + 1] then
		ret[j], ret[j + 1] = ret[j + 1], ret[j] --# swap the values
	  end
	end
  end
  --# return our new table
  return ret
end

Thanks, after I typed that out I realized that tables might be stored that way. The way I was taught is that there are two memory structures, the stack and the heap, elements on the "stack" are unique and when you do stackedElement = anOtherStackedElement changing stackedElement wont change the original, but if they are on the "heap" they are just pointers to pieces of data in a "heap" and when you do heapedElement = anOtherHeapedElement that just makes heapedElement point to the same place as anOtherHeapedElement and changing heapedElement changes the data that heapedElement points to and therefore also changes anOtherHeapedElement. Are "stack" and "heap" common terms?

happydude11209, on 07 June 2013 - 03:22 PM said:

Are "stack" and "heap" common terms?

Yes, stack and heap are the terms used by programmers.

table.sort is really the way to go here, for anything other than playing around with sorting algorithms.

Lyqyd, on 07 June 2013 - 08:45 PM said:

table.sort is really the way to go here, for anything other than playing around with sorting algorithms.

Thanks! I have switched over :)/>

Also it should be noted that with table.sort you can also define your own comparison function. Why would you want to? Well what if you have tables, and want to sort the main table, say based off an ID in the sub table, this is where the function comes in handy.

t = {
{ ID = 2 },
{ ID = 1 },
}

table.sort(t, function( a, b ) return a.ID > b.ID end)

Yeah I knew that :)/> I just was using table.sort wrong every time I had run tests and always got errors, so I had decided to write my own. Thanks everyone for all the help!