User:Dora Gustafson/insertion sort

Straight insertion Sort

The effective straight insertion sort routine for LSL is included

First is the most simplified edition

<lsl> insertionSort() {

   integer i;
   integer j;
   for ( i=1; i<llGetListLength(Lcrit); i++)
   {
       j=i;
       while ( llList2Integer( Lcrit, j-1)>llList2Integer( Lcrit, i) && j>0) --j;
       if (j<i) Lcrit=llListReplaceList( Lcrit, llList2List( Lcrit, i, i)+llList2List( Lcrit, j, i-1), j, i);
   }

}</lsl> It will sort a list: Lcrit, of numbers in ascending order
This simple edition can easily be expanded to sort parallel lists something that can't be done with the built in llListSort()

Then a full version that can sort a strided list and take the same parameters as the built in llListSort() does

<lsl> list insertionSort( list src, integer stride, integer ascending) {

   integer i;
   integer j;
   integer k = llGetListLength(src);
   if (ascending) for ( i=stride; i<k; i+=stride)
   {
       j=i;
       while ( llList2Float( src, j-stride)>llList2Float( src, i) && j>0) j -= stride;
       if (j<i) src=llListReplaceList( src, llList2List( src, i, i+stride-1)+llList2List( src, j, i-1), j, i+stride-1);
   }
   else for ( i=stride; i<k; i+=stride)
   {
       j=i;
       while ( llList2Float( src, j-stride)<llList2Float( src, i) && j>0) j -= stride;
       if (j<i) src=llListReplaceList( src, llList2List( src, i, i+stride-1)+llList2List( src, j, i-1), j, i+stride-1);
   }
   return src;

}</lsl> The straight insertion sort method has great advantages over the bubble sort method, but in lsl the competition isn't even.

The llListSort() is normally a factor 10 to 100 times faster.

When sorting lists that are in order or almost in order, this sort and the built in are almost doing the job at the same speed.

Lists used for testing had 100 strides with three elements in each

This routine can sort on numbers only! A>B and A<B are only defined in LSL for numbers