Sorting A Table With Sub-Tables

I am trying to optimize the movement of a turtle between points stored in a table.

The structure is:

t = {[index] = {x, y}}

I would like my table table look like this after the sort:

t = {[1] = {5, 0}
	  [2] = {6, 0}
	  [3] = {7, 0}
	  [4] = {7, 1}
	  [5] = {6, 1}
	  [6] = {5, 1}
	  [7] = {5, 2}
	  [8] = {6, 2}
	  [9] = {7, 2}
	  [10] = {6, 3}
	  [11] = {5, 3}
	  [12] = {4, 3}
	  Etc.
	  }

To be a bit clearer;
y should be sorted from low to high
x should alternate from low to high and high to low for a given y series

Yes, table.sort() exists and looks like the tool for the job. But how do I use it?

Thanks

I'm thinking this might work:

table.sort(t, function( a, b )
  if a[2] < b[2] then      --# if the first y is less than the second y...
    return a[2] < b[2]     --# sort these least to greatest
  elseif a[2] > b[2] then  --# if the first y is greater than the second y...
    return a[2] > b[2]     --# sort these greatest to least
  else                     --# if they are equal...
    if a[2] % 2 == 0 then     --# if the y is even...
      return a[1] < b[1]      --# sort least to greatest
    else                      --# if the y is odd...
      return a[1] > b[1]      --# sort greatest to least
    end
  end
end)

The function you give to table.sort works on the principle of comparing and sorting each item individually. In that function, all you have to really think about is sorting the current two items that are given to you, and lua will have the table in the correct order.

Returning "a < b" sorts the first item before the second, least to greatest. "a > b" Sorts second before first, greatest to least.

If you pass table sort a function it sends it 2 options, a and b in this case. If the function returns true it puts a before b and vice versa. You don't really need all of those if statements, just use

table.sort(t,function( a,b ) return a[2]<b[2] end)

if you want to make it sort the y and then the x if the y is equal use

table.sort(t,function( a,b ) return a[2]<b[2] or (a[2]==b[2] and a[1]<b[1])  end)

with the second method you will end with

t = {[1] = {5, 0}
	  [2] = {6, 0}
	  [3] = {7, 0}
	  [4] = {5, 1}
	  [5] = {6, 1}
	  [6] = {7, 1}
	  [7] = {5, 2}
	  [8] = {6, 2}
	  [9] = {7, 2}
	  [10] = {4, 3}
	  [11] = {5, 3}
	  [12] = {6, 3}
	  Etc.
	  }

and if needed you can actually make it sort them by distance from a point not at [0,0] etc

That's not really what he wanted though. He wanted to make it so that (in my terms) the x is sorted lowest to highest on and even y, and highest to lowest on an odd y.

The reason I used the multitude of ifs is because the logic there is much easier to comprehend.

if you look at his example of how he wanted it in the end though the x is not sorted at all

EDIT: Derp I guess I was just being blind. You are right. I'm so tired of my constant derpifying nowadays. Y U no work brain??

Thank you Kingdaro and Kaos.
I especially appreciate the line by line comments.

I hope I will have time this weekend to try your suggestions.

Would this be simpler?

if a[2] == b[2] then
  return a[2] % 2 == 0 and a[1] < b[1] or a[1] > b[1]
end
return a[2] < b[2]

It would. But again, I wanted to be perfectly clear with the usage of functions and table.sort.

BigTwisty, on 31 August 2013 - 05:48 PM said:

Would this be simpler?

if a[2] == b[2] then
  return a[2] % 2 == 0 and a[1] < b[1] or a[1] > b[1]
end
return a[2] < b[2]

No.

The lua idiom [conditional] and [if-true] or [if-false] falls apart when the if-true expression can evaluate to false.

Let's say that a[1] is greater than b[1]. That means our expression looks more like:

return a[2] % 2 == 0 and false or true

It should be pretty clear that if a[1] is greater than b[1], it will always return true, regardless of whether a[2] is even or odd.

So I messed with it some and this is what I am using:

table.sort(t, function(a, B)/>
return a[2] < b[2] or
  (a[2] == b[2] and a[2]%2 ~= 0 and a[1] < b[1]) or
  (a[2] == b[2] and a[2]%2 == 0 and a[1] > b[1])
end)

when I tried the code as posted by Kingdaro I got the error:
attempt to index local 'b' (a nil value)

The code by KaoS worked but did not sort x values as I wanted

Again thanks for all the help. My code is probably bad in several ways but it does the job. If you want to help some more please show me how my code is bad and why.

Thank you all

Lyqyd, on 31 August 2013 - 08:27 PM said:

The lua idiom [conditional] and [if-true] or [if-false] falls apart when the if-true expression can evaluate to false.

Good catch. Working from my iphone it's tough to see stupid things like that sometimes. :)/>