Forum

> > CS2D > Scripts > Sorted Iteration?
Forums overviewCS2D overview Scripts overviewLog in to reply

English Sorted Iteration?

13 replies
To the start Previous 1 Next To the start

old Sorted Iteration?

mozilla1
User Off Offline

Quote
I have thought about something like that.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
tbl={
["data1"]=39,
["data2"]=30,
["data3"]=29,
["data5"]=21,
["data10"]=9,
["data12"]=7,
["data14"]=40,
["data19"]=16,
}

for index in sorted_pairs(tbl) do
	print(tbl[index])
end

-- Output

7
9
16
21
29
30
39
40


Is that possible? A function that iterates over a table, in sorted order?

EDIT: I want the table to be sorted by the values, not by the keys, sorry.
edited 4×, last 16.11.13 01:16:35 am

old Re: Sorted Iteration?

Rainoth
Moderator Off Offline

Quote
table.sort

I'll post the information about it in a more tag, hopefully I'm using it correctly.

More >

old Re: Sorted Iteration?

mozilla1
User Off Offline

Quote
user Rainoth has written
table.sort

I'll post the information about it in a more tag, hopefully I'm using it correctly.

More >


Sorry if I wasn't being clear...
But table.sort only sorts a table by their index, I want to be sorted by the values, rather than indexing.

old Re: Sorted Iteration?

Rainoth
Moderator Off Offline

Quote
I guess you could use math.max function to find highest value in table, then store it in another table and remove from the first one, then use math.max again and in this way all your old table values would be transfered to new table which ranges from highest to lowest.

old Re: Sorted Iteration?

Flacko
User Off Offline

Quote
You need a second table where the keys are integers and the values are the keys from tbl ("data1", ..., "data19"):
1
2
3
4
local tbl2 = {}
for k, v in pairs(tbl) do
	table.insert(tbl2, k)
end
Then you can sort tbl2 using any sorting algorithm of your choice. However, when comparing two values, you have to compare with an extra level of indirection: tbl[tbl2[i]] < tbl[tbl2[j]].
When you want to iterate:
1
2
3
for i = 1, #tbl2 do
	--do something with tbl[tbl2[i]]
end

old Re: Sorted Iteration?

mozilla1
User Off Offline

Quote
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function table.vsort(tbl)
	local tbl=tbl
	local tbl2 = {}
	for k, v in pairs(tbl) do
		table.insert(tbl2, k)
	end
	
	local index=0
	local j=0

	for i = 1, #tbl2 do
		--do something with tbl[tbl2[i]]
		index=tbl[tbl2[i]]
		j=i-1
		while ((j>=1) and (tbl[tbl2[j]] > index)) do
			tbl[tbl2[j+1]]=tbl[tbl2[j]]
			j=j-1
		end
		tbl[tbl2[j+1]] = index
	end
	
	return tbl
end


I guess this will do the work. I used the "Insertion sort" algorithm.

Yep it's simple... but I will use it until I get a better sorter.
Thanks @user Flacko:

old Re: Sorted Iteration?

Flacko
User Off Offline

Quote
Np, but you could also use the table.sort function and save up some code:
1
2
3
4
local f = function(a,b)
	return tbl[a] < tbl[b]
end
table.sort(tbl2, f) // i believe this uses an implementation of quicksort

Btw:
1
local tbl=tbl
This line won't do anything since tbl is already a local variable (actually a parameter, but the lua vm deals with them in the same way)

old Re: Sorted Iteration?

VaiN
User Off Offline

Quote
here's another example. this is using luafilesystem to get the files in a directory and sort them alphabetically.

1
2
3
4
5
6
7
8
9
10
lfs = require"lfs"
local filelist = {}
local int = 1
for file in lfs.dir("/path/to/files/") do
	if file ~= nil and file ~= "." and file ~= ".." then
		filelist[int] = file
		int = int + 1
	end
end
table.sort(filelist, function (a,b) return (a > b) end)

edit: my previous example was sorting keys, this will sort the values as requested

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
tbl={
	["data1"] = 39,
	["data2"] = 30,
	["data3"] = 29,
	["data5"] = 21,
	["data10"] = 9,
	["data12"] = 7,
	["data14"] = 40,
	["data19"] = 16,
}

-- first add to a new table swapping keys and values
-- then we add just the values to an ordered table
sorted = {}
swapped = {}
int = 1
for k,v in pairs(tbl) do
	swapped[v] = k
	sorted[int] = v
	int=int+1
end
-- this will be in acending order, switch "<" to ">" for decending
table.sort(sorted, function (a,b) return (a < b) end)

-- now we can iterate throught the sorted table
for i=1,#sorted do
	-- print the original values in order
	print(sorted[i])
	
	-- this gives us the original keys, sorted by the original values
	print(swapped[sorted[i]])
end

there's probably an easier way, but this one makes the most sense for me
edited 3×, last 16.11.13 09:16:05 am

old Re: Sorted Iteration?

mozilla1
User Off Offline

Quote
@user VaiN: Your implementation seems to work more accuraotely.

I realized that my code only swap the values, not the keys, and you came here with the solution.

Thanks in advance.

EDIT: The for iterator, that sorts through table values.
EDIT2: If there are two same values, the key get duplicated... Dunno how to fix it...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function sorted_pairs(tbl)
	local sorted={}
	local swapped={}
	local int=1
	
	for k,v in pairs(tbl) do
		swapped[v] = k
		sorted[int] = v
		int=int+1
	end
	table.sort(sorted, function (a,b) return (a < b) end)
	
	local n=0
	local function sorting(state)
		if n<state then
			n=n+1
			return swapped[sorted[n]],sorted[n]
		end
	end
	return sorting,#sorted,0
end

for v1,v2 in sorted_pairs(tbl) do
	print(v1.."|"..v2)
end
edited 2×, last 16.11.13 04:13:14 pm

old Re: Sorted Iteration?

Flacko
User Off Offline

Quote
This might be a slightly better implementation since it only uses one extra table:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
tbl = {
	data1 =39,
	data2 = 30,
	data3 = 29,
	data5 = 21,
	data6 = 16,
	data10 = 9,
	data12 = 7,
	data14 = 40,
	data19 = 16,
}

local sortedPairs = function(t)
	local tk = {}
	for k, v in pairs(t) do
		tk[#tk+1] = k
	end
	table.sort(tk,
		function(a, b) return t[a] < t[b] end
	)
	local i = 0
	return function()
		i = i + 1
		if tk[i] then
			return tk[i], t[ tk[i] ]
		end
	end
end

for k, v in sortedPairs(tbl) do
	print(k, v)
end

Duplicate values were causing you trouble because you used values as keys in your 'swapped' table.

old Re: Sorted Iteration?

VaiN
User Off Offline

Quote
ah good catch on that. i hadn't thought about duplicates.

edit:
Thanks user Flacko for pointing out that you can actually just sort the values directly with the table.sort function. His example is perfect for what you seek.

here's a rewrite of my approach in case anyone is interested:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
tbl = {
	data1 = 39,
	data2 = 30,
	data3 = 29,
	data5 = 21,
	data6 = 16,
	data10 = 9,
	data12 = 7,
	data14 = 40,
	data19 = 16,
}

function sorted(t,direction)
	ts = {}
	for k,v in pairs(t) do
		ts[ #ts + 1 ] = { key = k, value = v }
	end
	if direction == "a" then
		table.sort(ts, function (a,b) return (a.value < b.value) end)
	elseif direction == "d" then
		table.sort(ts, function (a,b) return (a.value > b.value) end)
	end
	return ts
end

tbl = sorted(tbl,"a")
for i=1,#tbl do
	print( tbl[i].key, tbl[i].value )
end
output:
1
2
3
4
5
6
7
8
9
data12	7
data10	9
data19	16
data6	 16
data5	 21
data3	 29
data2	 30
data1	 39
data14	40
this gives you the option of having a sorted table returned (with option of ascending or decending), and you can iterate by index instead of key/value if you prefer.
edited 1×, last 17.11.13 06:42:08 am

old Re: Sorted Iteration?

KimKat
GAME BANNED Off Offline

Quote
This may help. I coded a neat function here that reads table indexes and outputs their data.
t={["data"]=0,["data"]=1,["data"]=2,["data"]=3,["data"]=4,["data"]=5,["data"]=6,["data"]=7,["data"]=8,["data"]=9}
function count(t,l) l=l or #t;for var=0,l,1 do print(var) end end
count(t,7) -- Prints indexes up to 7.
count(t,1) -- Prints index 1.

old Re: Sorted Iteration?

mozilla1
User Off Offline

Quote
Thanks guys. It worked perfectly.
If you guys want to discuss more about this, can keep this topic opened.
To the start Previous 1 Next To the start
Log in to reply Scripts overviewCS2D overviewForums overview