Difference between revisions of "User:Dora Gustafson/insertion sort"
Jump to navigation
Jump to search
(straight insertion sort routine) |
|||
| Line 15: | Line 15: | ||
}</lsl> | }</lsl> | ||
It will sort a list: Lcrit, of numbers in ascending order<br> | It will sort a list: Lcrit, of numbers in ascending order<br> | ||
This simple edition can easily be expanded to sort parallel lists something that can't be done with the built in llListSort() | This simple edition can easily be expanded to sort parallel lists something that can't be done with the built in [[LlListSort|llListSort()]] | ||
: Then a full version that can sort a strided list and take the same parameters as the built in llListSort() does | : Then a full version that can sort a strided list and take the same parameters as the built in [[LlListSort|llListSort()]] does | ||
<lsl> | <lsl> | ||
list insertionSort( list src, integer stride, integer ascending) | list insertionSort( list src, integer stride, integer ascending) | ||
| Line 38: | Line 38: | ||
}</lsl> | }</lsl> | ||
The straight insertion sort method has great advantages over the bubble sort method, but in lsl the competition isn't even. | 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. | : The [[LlListSort|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. | : 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<br> | : Lists used for testing had 100 strides with three elements in each<br> | ||
This routine can sort on numbers only! A>B and A<B are only defined in LSL for numbers | This routine can sort on numbers only! A>B and A<B are only defined in LSL for numbers | ||
{{LSLC|Library}} | {{LSLC|Library}} | ||
Revision as of 11:10, 16 September 2013
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