Sorting parallel lists

[Dora Gustafson]

The method used is Insertion Sort
It is described in details and compared to other methods on this Wikipedia
LSL has one sorting routine: llListSort() for strided lists, which should be preferred for the one I present here whenever possible.
llListSort() can sort string elements in a list, which is very hard to do in any other way.

The Insertion Sort routine to the bone looks like this in LSL:

1. insertionSort()
2. {
3.     integer i;
4.     integer j;
5.     for ( i=1; i<llGetListLength(Lcrit); i++)
6.     {
7.         j=i;
8.         while ( llList2Integer( Lcrit, j-1)>llList2Integer( Lcrit, i) && j>0) --j;
9.         if (j<i) Lcrit=llListReplaceList( Lcrit, llList2List( Lcrit, i, i)+llList2List( Lcrit, j, i-1), j, i);
10.     }
11. }

This routine can sort one list of integers: list Lcrit;
In line 5 all elements except the first are indexed one by one
in line 8 it is found out where the element fits in in elements with lower index
in line 9 the element is moved into place if it needs to be moved

In the following the method is utilized in a working test script
The test script sorts one list of integers and synchronize three lists with the sorted list

// sorting parallel synchronized lists by Dora Gustafson, Studio Dora 2011
// All elements in the list with the sorting criteria must have same type
// The routine accepts integer or float types
// insertion sort used
// reference: http://en.wikipedia.org/wiki/Sorting_algorithm#Insertion_sort

list Lcrit=[ 3,5,11,11,15,17];
list Lpar2=[3.14,5.5,11.1,11.2,15.5,17.6];
list Lpar3=["three","five","11 one","11 two","fifteen","seventeen"];
list Lpar4=[3.00,"five",11,<1,0,0>,"Second",<0.0, 0.0, 0.0, 1.0>];

insertionSort()
{
    integer i;
    integer j;
    integer eType=llGetListEntryType(Lcrit, 0);
    for ( i=1; i<llGetListLength(Lcrit); i++)
    {
        j=i;
        if (eType==1) while ( llList2Integer( Lcrit, j-1)>llList2Integer( Lcrit, i) && j>0) --j;
        else if (eType==2) while ( llList2Float( Lcrit, j-1)>llList2Float( Lcrit, i) && j>0) --j;
        if (j<i)
        {
            Lcrit=llListReplaceList( Lcrit, llList2List( Lcrit, i, i)+llList2List( Lcrit, j, i-1), j, i);
            Lpar2=llListReplaceList( Lpar2, llList2List( Lpar2, i, i)+llList2List( Lpar2, j, i-1), j, i);
            Lpar3=llListReplaceList( Lpar3, llList2List( Lpar3, i, i)+llList2List( Lpar3, j, i-1), j, i);
            Lpar4=llListReplaceList( Lpar4, llList2List( Lpar4, i, i)+llList2List( Lpar4, j, i-1), j, i);
        }
    }
}

showlists()
{
    integer n;
    for ( n=0; n<llGetListLength(Lcrit); n++)
    llOwnerSay( llList2String( Lcrit, n)+", "+llList2String( Lpar2, n)+", "+llList2String( Lpar3, n)+", "+llList2String( Lpar4, n));
}

default
{
    touch_end( integer p)
    {
        Lcrit = llListRandomize( Lcrit, 1 );
        Lpar2 = llListRandomize( Lpar2, 1 );
        Lpar3 = llListRandomize( Lpar3, 1 );
        Lpar4 = llListRandomize( Lpar4, 1 );
        showlists();
        insertionSort();
        llOwnerSay("Sorted:");
        showlists();
    }
}

 Notes:

1. The procedure works with global lists
2. The procedure must be modified to adopt a different number of parallel lists
3. The sorted list must have integer or float elements only and
   the elements can not be entered as strings because llGetListEntryType() is used
4. Can not sort string elements! ( string1>string2 is not defined in LSL)
5. A sorting of parallel lists can not be done by one general procedure called with parameters in LSL
   (as far as I see)

 

[Void Singer]

hah, nice, beat me to the punch. wanna tackle multisorting (any of the parallel lists with same types) next?

[Dora Gustafson]

I picked up the ball from your todo list in this thread

Now I play it back to you:smileyvery-happy:

[Void Singer]

tag I'm it, huh? =P

[PeterCanessa Oh]

Mmmmm, sorting :-) Computing's "better mousetrap" :-)

Two functions to sort any number of parallel-lists, any data-types, based on any list you care to use:

 

// Multisort// =========// Functions to synchronise sorting amongst parallel lists// SortStart():	sorts a list and stores the original indices for use in SortSync()// SortSync(): uses the original indices from SortStart() to sort parallel listslist SortIndices;list SortStart(list MasterList, integer Ascending){	// Build strided list with element indices	integer Element;	list SortList;	for(Element = 0; Element < llGetListLength(MasterList); Element++){		SortList += llList2List(MasterList, Element, Element);		SortList += Element;	}	// Sort it, 'de-stride' into lists of (sorted) data and (original) indices	SortList = llListSort(SortList, 2, Ascending);	MasterList = llList2ListStrided(SortList, 0, -1, 2);	SortIndices = llList2ListStrided(llDeleteSubList(SortList, 0, 0), 0, -1, 2);	return MasterList;}list SortSync(list ParallelList){	integer Element;	integer From;	list SortList;	for(Element = 0; Element < llGetListLength(SortIndices); Element++){		From = llList2Integer(SortIndices, Element);		SortList += llList2List(ParallelList, From, From);	}	return SortList;}default{    state_entry(){    	// Usage: Call SortStart() with the list to use for sorting, then call SortSync() with each of the parallel lists    	list AList;    	list AnotherList;    	list AndAnotherList;    	AList = SortStart(AList, TRUE);    	AnotherList = SortSync(AnotherList);    	AndAnotherList = SortSync(AndAnotherList);    }}

 

Untested and (possibly) not even properly thought-through.  The idea is the SortStart() creates a list of the original indices while sorting the first parallel-list.  Each time SortSync() is called - for each of the other parallel-lists - it uses this list of original indices to put the corresponding elements into the same order.

Sanity check please.

[PeterCanessa Oh]

A refinement occurs to me ...

• Define SortIndices as local to where lists are used, not as a global
• Edit SortStart() to return list of indices instead of the first sorted list
• Edit SortSync() to accept a second parameter; being the list of indices to use (as now returned from SortStart())
• Call SortSync() for the first parallel list as well as the others

Although this means sorting the first parallel list twice (once each in SortStart() and SortSync()) it allows for multiple sorts on multiple sets of parallel lists - just store and pass around the relevant set of original indices.

 

// Multisort// =========// Functions to synchronise sorting amongst parallel lists// SortStart():	sorts a list and returns the original indices for use in SortSync()// SortSync(): uses the original indices from SortStart() to sort parallel listslist SortStart(list MasterList, integer Ascending){	// Build strided list with element indices	integer Element;	list SortList;	for(Element = 0; Element < llGetListLength(MasterList); Element++){		SortList += llList2List(MasterList, Element, Element);		SortList += Element;	}	// Sort it and return (original) indices	SortList = llListSort(SortList, 2, Ascending);	return llList2ListStrided(llDeleteSubList(SortList, 0, 0), 0, -1, 2);}list SortSync(list ParallelList, list SortIndices){	integer Element;	integer From;	list SortList;	for(Element = 0; Element < llGetListLength(SortIndices); Element++){		From = llList2Integer(SortIndices, Element);		SortList += llList2List(ParallelList, From, From);	}	return SortList;}default{    state_entry(){    	// Usage: Call SortStart() with the list to use for sorting, then call SortSync() with each of the parallel lists    	list Set1List1;    	list Set1List2;    	list Set1List3;    	list Set2List1;    	list Set2List2;    	list Set2List3;    	list Set2List4;    	list Indices1 = SortStart(Set1List1, TRUE);    	Set1List1 = SortSync(Set1List1, Indices1);    	// NB: It doesn't matter what order you sort lists and sets of lists as long as you use the right set of indices from SortStart()    	list Indices2 = SortStart(Set2List3, FALSE);    	Set2List1 = SortSync(Set2List1, Indices2);    	Set2List2 = SortSync(Set2List2, Indices2);    	Set2List3 = SortSync(Set2List3, Indices2);    	Set2List4 = SortSync(Set2List4, Indices2);    	Set1List2 = SortSync(Set1List2, Indices1);    	Set1List3 = SortSync(Set1List3, Indices1);    }}

 

And now I've had several cups of coffee and the brain is firing-up properly ... here's a bit of fun that arises 'for free':  By calling SortStart() on a list of indices instead of a parallel list you get an 'unsort' option.  That is:

• Indices = SortStart(DataList, TRUE);
• Unsort = SortStart(Indices, TRUE);
• SortedData = SortSync(DataList, Indices);
• BackToOriginal = SortSync(SortedData, Unsort);

 

[PeterCanessa Oh]

Erm ... I worry a bit when I find I'm posting three times in succession, plus edits, on the same thread.  Oh well, my first one here did say I hadn't thought it through yet.

What these routines and the stored list of indices add up to is an ISAM-style database lookup.  When you have the indices like this it is often not necessary to spend the processing time on actually sorting all the parallel lists, just do an indexed-reference.  This is especailly important when you may be using multiple sort-orders on a single set of data.  In this case it would obviously be time-consuming and wasteful to keep re-sorting everything.  As a simple example assume lists of Names and Ages.

• list Alpha = SortStart(Names, TRUE);
• list Numeric = SortStart(Ages, TRUE);
• string FirstAlphabeticName = llList2String(Names, llList2Integer(Alpha, 0)); // } Name and age of the first person in akphabetical
• integer FirstAlphabeticAge = llList2Integer(Ages, llList2Integer(Alpha, 0));  // } order
• string SecondOldestPerson = llList2String(Names, llList2Integer(Numeric, -2)); // } Name and age of the penultimate person in
• integer SecondOldestAge = llList2Integer(Ages, llList2Integer(Numeric, -2));   // } age order

[Void Singer]

I guess that makes us even for me clearing your may schedule