Difference between revisions of "LlListSort"

From Second Life Wiki
Jump to navigation Jump to search
Line 22: Line 22:
// returns ["1ag", "2ae" ,"3ac" ,"4af" ,"aa6" ,"ab8" ,"ad7" ,"ah5" ,"ai9"]</lsl>
// returns ["1ag", "2ae" ,"3ac" ,"4af" ,"aa6" ,"ab8" ,"ad7" ,"ah5" ,"ai9"]</lsl>
|caveats=*A bubble sort is a sorting algorithm with a Big O of N*N. Why Linden Lab did not use a N*log(N) sorting algorithm such as [http://en.wikipedia.org/wiki/Heapsort Heap Sort] or [http://en.wikipedia.org/wiki/Mergesort Merge Sort] is unknown. A [[JIRA]] issue exists to improve this function, [http://jira.secondlife.com/browse/SVC-2988 vote for it here].
|caveats=*A bubble sort is a sorting algorithm with a Big O of N*N. Why Linden Lab did not use a N*log(N) sorting algorithm such as [http://en.wikipedia.org/wiki/Heapsort Heap Sort] or [http://en.wikipedia.org/wiki/Mergesort Merge Sort] is unknown. A [[JIRA]] issue exists to improve this function, [http://jira.secondlife.com/browse/SVC-2988 vote for it here].
* Originally the wiki stated that non-zero values for the "ascending" parameter would produce an ascending sort.  That was incorrect.  For this function, the value must be exactly 1 (or TRUE) for an ascending sort.
* Vectors are sorted by magnitude. {{Jira|SVC-5643}}
* Vectors are sorted by magnitude. {{Jira|SVC-5643}}
|constants
|constants

Revision as of 20:29, 4 November 2011

Summary

Function: list llListSort( list src, integer stride, integer ascending );
0.0 Forced Delay
O(N2) Compl.
10.0 Energy

Returns a list that is src sorted by stride.

• list src List to be sorted.
• integer stride number of entries per stride, if less then 1 it is assumed to be 1.
• integer ascending if TRUE then the sort order is ascending, otherwise the order is descending.

This function supports Strided Lists.

Specification

A slow bubble sort is employed to perform the sort.
The sort order is affected by type and is case sensitive.
<lsl>llListSort(["a", "B", "C", "d", "e"], 1, TRUE) // returns ["B", "C", "a", "d", "e"]</lsl> Each type is sorted individually and then feathered to have the same order of types. <lsl>llListSort([1, "C", 3, "A", 2, "B"], 1, TRUE) // returns [1, "A", 2, "B", 3, "C"]

llListSort([1, 3, 2, "C", "A", "B"], 1, TRUE) // returns [1, 2, 3, "A", "B", "C"]

llListSort([1, "C", 3, "A", 2, "B"], 2, TRUE) // returns [1, "C", 2, "B", 3, "A"]

llListSort(["2ae", "ah5", "1ag", "aa6", "3ac", "ad7", "ab8", "4af", "ai9"], 1, TRUE); // returns ["1ag", "2ae" ,"3ac" ,"4af" ,"aa6" ,"ab8" ,"ad7" ,"ah5" ,"ai9"]</lsl>

Caveats

  • A bubble sort is a sorting algorithm with a Big O of N*N. Why Linden Lab did not use a N*log(N) sorting algorithm such as Heap Sort or Merge Sort is unknown. A JIRA issue exists to improve this function, vote for it here.
  • Originally the wiki stated that non-zero values for the "ascending" parameter would produce an ascending sort. That was incorrect. For this function, the value must be exactly 1 (or TRUE) for an ascending sort.
  • Vectors are sorted by magnitude. SVC-5643

Examples

<lsl> list numbers = [3, "three", 2, "two", 1, "one"]; default {

   state_entry()
   {
       llOwnerSay(llDumpList2String(numbers, ","));
       // Object: 3,three,2,two,1,one
       numbers = llListSort(numbers, 2, TRUE);
       llOwnerSay(llDumpList2String(numbers, ","));
       // Object: 1,one,2,two,3,three
   }

} </lsl>

Video Tutorial

<videoflash type="youtube">BNIUHnpeUQs|640|385</videoflash>

Notes

Data Types

llListSort really only works on items of the same type. It will work on lists that hold diverse data types -- to be clear, it won't blow up your script -- but the results returned are usually meaningless.

<lsl>list mylist = ["brown", <0.000000, 0.000000, 0.000000>, "house", 17.005, 100, "cat", <3.000000, 3.000000, 3.000000>, 39]; list tmplist = llListSort(mylist, 1, TRUE); llSay(0, llList2CSV(tmplist));</lsl>

This returns in chat:

brown, <0.000000, 0.000000, 0.000000>, cat, 17.004999, 39, house, <3.000000, 3.000000, 3.000000>, 100

Utilizing the Results

It's important to note that the source list that you are sorting will remain unchanged. Instead, a new, sorted list will be produced. So, it's important that you capture this with a variable (unless you are acting directly on the results.)

<lsl>llListSort(myList, 1, TRUE); // You've wasted cpu time; you didn't capture the results

list newlist = llListSort(myList, 1, TRUE);// Okay. You've captured the results.

llSay(0,llList2CSV(llListSort(myList, 1, TRUE))); // No need to capture, using the results right away.</lsl>

Stride parameter

Most times, you will want to set "integer stride" to 1 (0 also works) to tell it to sort each item in the list on its own basis. (If you are working with a strided list, though, see the special section below on sorting strides.)

Sort Order

Setting the parameter "integer ascending" to TRUE returns a sorted list that is in ascending order.
For example: ["Apples", "Bananas", "Oranges"]

Setting the parameter "integer ascending" to FALSE returns a sorted list that is in descending order.
For example: ["Oranges", "Bananas", "Apples"]

Sorting Strided Lists

If you have a strided list, in which you are keeping related pieces of data together in chunks, letting each list element sort on its own basis would be disastrous.

<lsl>list demographics = ["John Adams", "male", "2007-06-22", "Shirley Bassey", "female", "2005-11-02", "Matt Damon", "male", "2008-05-19"];</lsl>

Bad Example

<lsl>list tmplist_1 = llListSort(demographics, 1, TRUE); //tmplist_1 == ["2005-11-02", "2007-06-22", "2008-05-19", "John Adams", "Matt Damon", "Shirley Bassey", "female", "male", "male"] //The strides have been destroyed, the sorted data is now useless</lsl>

Good Example

Instead, because you have the data grouped (aka "strided") in sets of 3, you need to do this:

<lsl>list tmplist_2 = llListSort(demographics, 3, TRUE); //templist_2 = ["John Adams", "male", "2007-06-22", "Matt Damon", "male", "2008-05-19", "Shirley Bassey", "female", "2005-11-02"] </lsl>

When storing data in strided lists, it's often worth it down the road to take a moment at the outset to think about how you are most likely to want to sort them, if ever the need arose. Remember, you can only sort on the first element in each group of elements. If you think you're mostly likely to want to sort on gender (to use the above list example), you should make gender the first element in the data grouping.

See Also

Functions

•  List: Get Reverse Order Returns a list that is src in reverse order.
•  LlDialog#Examples llListSort can be very useful for arranging buttons for llDialog

Deep Notes

Source

Signature

function list llListSort( list src, integer stride, integer ascending );