Game Maker Games, Articles, Tutorials & More

Print

ds_list_sort_ext

By Daniel · December 26, 2008

This script sorts a list using a given quantifier script. This should be a 1-ary script which takes a list element as input and returns a real value that can be used in sorting.

For example, say you wanted to sort a list so that the odd entries appeared before the even ones. You could write a basic function called is_odd and call ds_list_sort_ext(someList, false, is_odd). is_odd would return 1 for all the odd entries and 0 for the even ones. The script would use these values for the purpose of sorting, and since we told it to sort in descending order, the entries for which is_odd returned 1 would appear before the entries for which is_odd returned 0.

The algorithm used is merge sort. The script never creates additional helper lists (as most implementations do), so the code is a bit more complex but it avoids a great deal of overhead processing.

// ds_list_sort_ext(id, ascending, quantifier)
// Sorts a list using the given quantifier script. This should be a 1-ary
// script which takes a list element as input and returns a real value that
// can be used in sorting. The algorithm used is merge sort.

var L, asc, quant, size, extended_size, block_size, start, finish,
    stor1, stor2, stor1_size, stor2_size, stor1_pos, stor2_pos,
    E, E1, E2, E1_quant, E2_quant, i;

L     = argument0;
asc   = argument1;
quant = argument2;

size = ds_list_size(L);
extended_size = sqr(ceil(sqrt(size))); // nearest greater power of two

// Iterate through the list numerous (log n) times
for (block_size = 1; block_size < extended_size; block_size *= 2) {
  
  // For each partition of the list
  for (start = 0; start < size; start += block_size * 2) {
    
    // Divide this superblock into two subblocks, stor1 and stor2
    stor1_size = min(block_size, max(size - start,              0));
    stor2_size = min(block_size, max(size - start - block_size, 0));
    finish = min(start + block_size * 2, size);
    for (i = start; i < finish; i += 1) {
      if (i < start + block_size)
        stor1[i - start] = ds_list_find_value(L, i);
      else
        stor2[i - start - block_size] = ds_list_find_value(L, i);
    }
    stor1_pos = 0; stor2_pos = 0;
    
    // Merge the two blocks, storing the result in the original list L
    for (i = start; i < finish; i += 1) {
      
      // Get the extremum
      if (stor1_pos >= stor1_size) { // stor1 is dry, must use stor2
        E = stor2[stor2_pos];
        stor2_pos += 1;
      }
      else if (stor2_pos >= stor2_size) { // stor2 is dry, must use stor1
        E = stor1[stor1_pos];
        stor1_pos += 1;
      }
      else { // neither store is dry -- pick the extremum
        E1 = stor1[stor1_pos];
        E2 = stor2[stor2_pos];
        E1_quant = script_execute(quant, E1);
        E2_quant = script_execute(quant, E2);
        
        if ((asc && E1_quant < E2_quant) || (!asc && E1_quant > E2_quant)) {
          // stor1 holds the extremum (E1)
          E = E1;
          stor1_pos += 1;
        }
        else {
          // stor2 holds the extremum (E2)
          E = E2;
          stor2_pos += 1;
        }
      }
      
      // Store the result
      ds_list_replace(L, i, E);
    }
  }
}

Categories: Data processing

Comments

There are no comments to display.

Post a Comment

You must be signed in to post comments.

Advertisement