Sorting

I need an efficient sorting system for my 3D renderer. I've been using selection sort (which is junk). I tried making quicksort, but I get a java error when I use recursive functions. How did you do it with merge sort? (I tried merge sort as well and it didn't work)

Edit by BB: thread split from here

Xelostar, on 29 August 2017 - 08:39 AM said:

I need an efficient sorting system for my 3D renderer. I've been using selection sort (which is junk). I tried making quicksort, but I get a java error when I use recursive functions. How did you do it with merge sort? (I tried merge sort as well and it didn't work)

Is there a reason you can't use Lua's table.sort? It's probably going to be quicker than any Lua implementation.

SquidDev, on 29 August 2017 - 08:49 AM said:

Xelostar, on 29 August 2017 - 08:39 AM said:

I need an efficient sorting system for my 3D renderer. I've been using selection sort (which is junk). I tried making quicksort, but I get a java error when I use recursive functions. How did you do it with merge sort? (I tried merge sort as well and it didn't work)

Is there a reason you can't use Lua's table.sort? It's probably going to be quicker than any Lua implementation.

I just got it to work. It was looping forever since I had 8 entries being equal. Made another array for the entries equal to the pivot. I bet it's faster to use table.sort, but the problem is I have a table of tables I want to sort (comparing a certain value inside the table inside the table). Do you know how I could get my code to work with table.sort()?

function quickSort(arrayToSort)
  local n = table.getn(arrayToSort)
  if (n <= 1) then
   return arrayToSort
  else
   local pivot = math.random(1, n)
   local pivotValue = arrayToSort[pivot].distance
   local smallerArray = {}
   local equalArray = {}
   local biggerArray = {}
   for k, v in pairs(arrayToSort) do
	if (v.distance < pivotValue) then
	 table.insert(smallerArray, v)
	elseif (v.distance == pivotValue) then
	 table.insert(equalArray, v)
	else
	 table.insert(biggerArray, v)
	end
   end
   local sortedSmallerArray = quickSort(smallerArray)
   local sortedBiggerArray = quickSort(biggerArray)
   local sortedArray = sortedBiggerArray
   for k, v in pairs(equalArray) do
	table.insert(sortedArray, v)
   end
   for k, v in pairs(sortedSmallerArray) do
	table.insert(sortedArray, v)
   end
  
   return sortedArray
  end
end

Xelostar, on 29 August 2017 - 11:24 AM said:

SquidDev, on 29 August 2017 - 08:49 AM said:

Is there a reason you can't use Lua's table.sort? It's probably going to be quicker than any Lua implementation.

I just got it to work. It was looping forever since I had 8 entries being equal. Made another array for the entries equal to the pivot. I bet it's faster to use table.sort, but the problem is I have a table of tables I want to sort (comparing a certain value inside the table inside the table). Do you know how I could get my code to work with table.sort()?

You can pass a comparison function, which returns if the first argument should appear before the second argument (so generally if the first is "less than" the second):

table.sort(arrayToSort, function(x, y) return x.distance < y.distance end)

I got an attempt to call nil, so I devided it into more lines to see where it was coming from.

function compare(x, y)
  return x.value < y.value
end

function sort(table)
  local sorted = table.sort(table, compare) -- < Error here
  return sorted
end

I tested and table isn't nil and compare isn't either. Any ideas?

table.sort is nil, because you rigged "table" to point to a different table than the one which holds the table API functions.

I understand. Thanks! :)/>

Xelostar, on 29 August 2017 - 12:58 PM said:

I understand. Thanks! :)/>

Why does your 3D rendering algorithm need sorting anyway? GPUs normally just render vertices in the order they're provided and use depth testing to avoid drawing a background vertex on top of a foreground vertex.

It's significantly faster to depth test a list of polygons a single time (while sorting them) than it is to do it once for every pixel on the screen. Yeah you can't have stuff like polys poking through other polys this way, but ComputerCraft doesn't have any sort of 3D acceleration. The necessary calculations would take forever to process.

Bomb Bloke, on 30 August 2017 - 03:36 AM said:

It's significantly faster to depth test a list of polygons a single time (while sorting them) than it is to do it once for every pixel on the screen. Yeah you can't have stuff like polys poking through other polys this way, but ComputerCraft doesn't have any sort of 3D acceleration. The necessary calculations would take forever to process.

I couldn't have spoken with better words. :)/>