Sorting numerical data to index

[Novo]

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!