User:Dora Gustafson/insertion sort - Revision history

Dora Gustafson at 20:37, 22 January 2015

2015-01-22T20:37:04Z

← Older revision		Revision as of 13:37, 22 January 2015
Line 2:		Line 2:
	The effective straight insertion sort routine for LSL is included		The effective straight insertion sort routine for LSL is included
	: First is the most simplified edition		: First is the most simplified edition
	<~~lsl~~>		<source lang="lsl2">
	insertionSort()		insertionSort()
	{		{
Line 13:		Line 13:
	if (j<i) Lcrit=llListReplaceList( Lcrit, llList2List( Lcrit, i, i)+llList2List( Lcrit, j, i-1), j, i);		if (j<i) Lcrit=llListReplaceList( Lcrit, llList2List( Lcrit, i, i)+llList2List( Lcrit, j, i-1), j, i);
	}		}
	}</~~lsl~~>		}</source>
	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\|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\|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~~>		<source lang="lsl2">
	list insertionSort( list src, integer stride, integer ascending)		list insertionSort( list src, integer stride, integer ascending)
	{		{
Line 36:		Line 36:
	}		}
	return src;		return src;
	}</~~lsl~~>		}</source>
	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\|llListSort()]] is normally a factor 10 to 100 times faster.		: The [[LlListSort\|llListSort()]] is normally a factor 10 to 100 times faster.

Dora Gustafson: /* Straight insertion Sort */

2013-09-16T19:10:18Z

Straight insertion Sort

← Older revision		Revision as of 12:10, 16 September 2013
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}}

Dora Gustafson: straight insertion sort routine

2013-09-16T18:30:29Z

straight insertion sort routine

New page

== 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<br>
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<br>
This routine can sort on numbers only! A>B and A<B are only defined in LSL for numbers
{{LSLC|Library}}