GMLscripts.com

Tsa05

Member

Registered: 2016-11-16

Posts: 13

sort_list_of_lists(); Also, quicksort.

As I understand it, GameMaker uses Quicksort to sort ds_lists. Cool!

Supposing I needed to Quicksort something else? Orrrrrrrrr, in this case, I have a very specific need: A ds_list filled with ds_lists, and I want to sort by size of list. Using ds_list_sort would sort by list reference number...gotta implement quicksort.

This is 2 scripts, and recursive:

Script sort_list_of_lists(list, low, high)

Expand///	@desc	Accepts a ds_list and sorts it via a partition function
///	@arg	{real}	list	List of list of arrays
///	@arg	{real}	low		Low value of list part
///	@arg	{real}	high	High value of list part
var pat = argument[0];
var low = argument[1];
var hig = argument[2];

if(low<hig){
	var part = sort_partition(pat, low, hig);
	sort_list_of_lists( pat, low, part-1);
	sort_list_of_lists( pat, part+1, hig);	
}

So, we sort around a partition value, then sort before and after. The sort happens in the next function:
Script sort_partition(list, low, high)

Expand///	@arg	{real}	List
///	@arg	{real}	low
///	@arg	{real}	high

var lis = argument[0];
var low = argument[1];
var hig = argument[2];

var pivot = ds_list_size(lis[|hig]);
var i = low-1;

for(var j=low; j<hig; j++){
	// If curr element is <= pivot
	var subLis = lis[|j];
	var sz = ds_list_size(subLis);
	if(sz <= pivot){
		i++;
		
		// Swap i and j
		var swap = lis[|i];
		lis[|i] = lis[|j];
		lis[|j] = swap;
		
		// Optional
		ds_list_mark_as_list(lis, i);
		ds_list_mark_as_list(lis, j);
		
	}
}

var swap = lis[|i+1];
lis[|i+1] = lis[|hig];
lis[|hig] = swap;

// Optional
ds_list_mark_as_list(lis, i+1);
ds_list_mark_as_list(lis, hig);

return (i+1);

Some fun little things here. The partition script sets pivot equal to the size of a list instead of the value of an entry because I want to sort by that. Similarly, the script has "var subLis = lis[|j];     var sz = ds_list_size(subLis);" and then compares sz to pivot. In a usual quicksort you'd just compare lis[|j] to pivot.

Other thing; in my particular implementation, I have a scenario where I want to have GMS clean up my lists for me--using ds_list_mark_as_list() causes GMS to know that whenever the parent list is destroyed, the child lists should be as well. But, ofc, GMS can't seem to detect when the lists it's moving around were already marked as lists, so I have to re-mark them each time I move them. Wooooooo