# User:Dora Gustafson/insertion sort

< User:Dora Gustafson

Jump to navigation
Jump to search
Revision as of 11:30, 16 September 2013 by Dora Gustafson (talk | contribs) (straight insertion sort routine)

## 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