Talk:LlListSort

Bubble Sort?

This script: <lsl> default {

   state_entry()
   {
       llOwnerSay(llList2CSV(llListSort([3,2,3,5,3,1,1,4], 2, TRUE)));
   }

} </lsl>

outputs

1, 4, 3, 5, 3, 1, 3, 2

both in LSO and in Mono. This means that the sort is not stable. Since stability is a characteristic of Bubble Sort, it looks like the claim of using Bubble Sort is not correct. --Pedro Oval 20:01, 5 April 2014 (PDT)

Good point. -- Strife ^{(talk|contribs)} 21:26, 5 April 2014 (PDT)

maybe... needs an extended example to see if LSL backwards ordering isn't the culprit
-- Void ^{(talk|contribs)} 22:19, 5 April 2014 (PDT)

If it's in reverse order, it's not stable either. The reverse would be 3,1,3,5,3,2 but the actual result is 3,5,3,1,3,2 --Pedro Oval 12:39, 6 April 2014 (PDT)

doh, you're right... comb sort perhaps? looking at the ordering exchange seems more likely than insertion
-- Void ^{(talk|contribs)} 17:20, 6 April 2014 (PDT)

Best option could be to pose this question on the scripting mail list, Kelly appears to prefer that channel for tech information dumps. The bubble sort presumption probably came from a function included with the viewer part of the source, but its comments describe list syntax and functions that never made it to LSL2. --ObviousAltIsObvious Resident 17:30, 6 April 2014 (PDT)

I think it was a semantic problem, the existing list functions don't leave any room for embedded lists. When they couldn't get pass-by-reference to work properly (assumption), they likely killed embedded lists because it didn't fit well in 16KiB.

Q: Why does the viewer source contain code that is obviously server LSL VM source code?

A: A bit of history, before the age of Mono, scripts were compiled by the client, and the viewer source included a copy of much of the server VM code. You have to remember that the viewer wasn't always open source, it's likely that the client and server code once existed in a single repository, that would be recompiled at the same time. When LL opensourced the viewer, they split the repository, but because of interdependence between the server and client code, some files were duplicated between the two repositories. LSL related files overtime diverged, largely driven by Mono's server side compilation. So while it may seem strange now that the viewer contains server source, it wasn't at the time the article was written.

-- Strife ^{(talk|contribs)} 19:08, 6 April 2014 (PDT)

It's probably not very polite to bring up this link, but it may shed some light on the reasons behind usage of Bubble Sort and the presumption that it was used in the server code: [1]. It mentions what it calls "type specific feathered sorting", which I assume it to mean the individual sorting of elements of each type. The code claims that "unoptimized bubble sort" is the only way to achieve it. I haven't given it much thought yet, but I wonder if comb sort, as mentioned by Void, would also preserve that ordering. --Pedro Oval 03:09, 8 April 2014 (PDT)

I think that 3 passes index, sort, write could do this as well. Miranda's comment in SVC-2988 suggests that there is some other kind of overhead in there. --ObviousAltIsObvious Resident 05:31, 8 April 2014 (PDT)

I've tried Quicksort and Comb Sort. My input list was [3,2,1,3,3,4,3,3,1,4,1,9,3,6] with stride 2. llListSort returns [1,3,1,4,1,9,3,3,3,2,3,4,3,6]. I could not reproduce this result with Comb sort, not even pre-inverting the array nor by pre-inverting, sorting descending and post-inverting it. I've tried two variations and all possible shrink values for this length. I've also tried with Quicksort with a decent amount of possible choices of pivot (first, central, last, median, and sorting the first, central and last elements, using several variations of < and <= for median and sorting), to no avail. --Pedro Oval 07:01, 8 April 2014 (PDT)

I wish I had more time to play with this. Going by what is typically found in LL code, my first guess would be "whatever the GNU library is using in std::sort". It could very well be a wrapper around that. Adding to fun, there are 2 major C++ libraries in GNU land, each uses a different approach. --ObviousAltIsObvious Resident 07:30, 8 April 2014 (PDT)

Boost? P.S. I've looked at opensim code. I have no problem with us documenting opensim functions etc. -- Strife ^{(talk|contribs)} 08:58, 8 April 2014 (PDT)

Same difference, as Boost uses std::sort: [2]. Digging a bit I have found this: Introsort#Implementations (Wikipedia) which made it sound like any attempt at reproducing the results without GNU libstdc++ was going to be too painful to be worth it. Then I've tried with the C++11 program below; it was sorted in a stable way, as the result is: "1,3, 1,4, 1,9, 3,2, 3,4, 3,3, 3,6, ". I'm willing to make more experiments but I'm out of ideas at the moment. Any suggestions? (P.S.: who chose the colors for the C++ highlighter? Yuck!) --Pedro Oval 09:30, 9 April 2014 (PDT)

<cpp>

1. include <iostream>
2. include <algorithm>
3. include <vector>

struct Rec {

   int key;
   int data;

};

bool sortByKey(const Rec &lhs, const Rec &rhs) { return lhs.key < rhs.key; }

int main() {

   std::vector<Rec> v = {{3,2},{1,3},{3,4},{3,3},{1,4},{1,9},{3,6}};
   std::sort(v.begin(), v.end(), sortByKey);
   for (Rec &n : v)
       std::cout << n.key << "," << n.data << ", ";
   std::cout << std::endl;
   return 0;

} </cpp>

tried substituting partial_sort (I think that bypasses the insertion sort libc++ likes to use on small sets), almost the same as LSL but not close enough. 1,4, 1,3, 1,9, 3,3, 3,2, 3,4, 3,6, --ObviousAltIsObvious Resident 15:34, 9 April 2014 (PDT)