Quote:
Originally Posted by Raeiphon
I'm terrible with this sort of stuff - not just in GS2 but in Python aswell.
I'm basically after a function that sifts through a list file (probably not the right term for gs2, but basically what I mean) and resorts the list so the index of said list matches to the contents being sorted in a ascending or descending order.
So basically, I feed it a list with the contents [11,24,55,9,17] and the variable to sort ascending, and it returns:
list[0] = 9
list[1] = 11
list[2] = 17
list[3] = 24
etc, etc
But not only that, I'd need the function to be able to do this and reassign two pieces of data, so each number would be linked to a string. (list[0] = "9, raeiphon" - picture a scoreboard as such) This would be easy if GS2 supported tuples, but I've been gone from the scripting scene for so long I can barely remember anything about it.
I'm not asking for a script that does exactly this. I'm asking for advice on what methods I should take to properly learn how to do this - what to read up on, what to think, what to sort. A script would be nice if it was properly commented and whatnot, but I doubt anyone would be willing to spare the time to do that, if it's as hard as I think it is.
There's probably a really simple way to do this too. -sigh-
|
The best you can expect from this is O(n*log(n)).
PHP Code:
function sort_list( initial_list ) {
sorted_list = {}; // Sorted List
// For every element in the initial list
for ( list_item: initial_list ) {
// Find Index for new item
low = 0;
high = sorted_list.size();
while ( low < high ) {
mid = low + int( (high - low) / 2 );
if ( sorted_list[mid] > list_item )
high = mid;
else if ( sorted_list[mid] < list_item )
low = mid + 1;
else low = high = mid;
}
// Add Item to appropriate index
sorted_list.insert( high, list_item );
}
// Return sorted list
return sorted_list;
}
function onCreated() {
initial_list = {11,24,55,9,17}; // To Sort
sorted_list = sort_list( initial_list ); // output: {9,11,17,24,55}
}
If you want to create a mapped list... Have each list item such that key => value is a struct {key,value}. Namely, element[0] == key.
PHP Code:
function sort_list( initial_list ) {
sorted_list = {}; // Sorted List
// For every element in the initial list
for ( list_item: initial_list ) {
// Find Index for new item
low = 0;
high = sorted_list.size();
while ( low < high ) {
mid = low + int( (high - low) / 2 );
if ( sorted_list[mid][0] > list_item[0] )
high = mid;
else if ( sorted_list[mid][0] < list_item[0] )
low = mid + 1;
else low = high = mid;
}
// Add Item to appropriate index
sorted_list.insert( high, list_item );
}
// Return sorted list
return sorted_list;
}
function onCreated() {
initial_list = {{11,"Foo"},{24,"Bar"},{55,"Bad"},{9,"Good"},{17,"Foo Foo"}}; // To Sort
sorted_list = sort_list( initial_list ); // output: {{9,"Good"},{11,"Foo"},{17,"Foo Foo"},{24,"Bar"},{55,"Bad"}}
}
I actually am using a linear-search for my dictionary objects on my server, but a binary search on a sorted list is a lot more efficient... I was going to write this sometime this week anyways.
Hope this helps!
11-21-2008, 06:37 PM
Linear Mode
