Help Requested

[Sphaerica]

I'm attempting to get the following code to work:

mylist=[ (0,2), (3,1), (0,0), (4,5) ]
mylist.sort(cmp=lambda x,y:x[1]-y[1])
print mylist

I had one problem which I fixed by modifying method.js to match
function.js in the line:

var numvarnames = varnames && varnames.length;

[I added "varnames &&" in case 'co_varnames' was undefined, as is the
case for a non-builtin function.]

Now mergesort is complaining that a (the first parameter, the array)
is undefined.

Where am I going wrong?

[Scott Graham]

A couple problems that need to be fixed:

src/list.js doesn't have name parameters defined, so the cmp kwarg won't work yet. mylist.sort(lambda x,y: x[1] - y[1]) will though.

The second problem is that src/mergesort.js doesn't look like it sorts properly! Sigh. Perhaps you can see what's wrong with it.

[Sphaerica]

I think I see the sort problem. I'll fix it tomorrow.

[Sphaerica]

Where did you get the in-place mergesort algorithm you used?
Everything I've seen says such algorithms are complex and sometimes
expensive.

I may just replace yours with a regular mergesort, or a quicksort.

[Sphaerica]

I threw the following quick sort code into place (I didn't want to use
a normal merge sort, in case very large lists are to be sorted... I
don't know how efficient javascript would be in constantly creating
and populating new arrays and using big chunks of memory, especially
if complex objects are involved):

Sk.mergeSort = function(arr, cmp, key, reverse) // Replaced by
quicksort
{
Sk.quickSort(arr, cmp, key, reverse)
}

Sk.quickSort = function(arr, cmp, key, reverse)
{
goog.asserts.assert(!key, "todo;");
goog.asserts.assert(!reverse, "todo;");

if (!cmp)
{
cmp = Sk.mergeSort.stdCmp;
}

var partition = function(arr, begin, end, pivot)
{
var tmp;
var piv=arr[pivot];

// swap pivot, end-1
tmp=arr[pivot];
arr[pivot]=arr[end-1];
arr[end-1]=tmp;

var store=begin;
var ix;
for(ix=begin; ix<end-1; ++ix) {
if(Sk.misceval.callsim(cmp, arr[ix], piv) < 0) { // arr[ix]<=piv) {
// swap store, ix
tmp=arr[store];
arr[store]=arr[ix];
arr[ix]=tmp;
++store;
}
}

// swap end-1, store
tmp=arr[end-1];
arr[end-1]=arr[store];
arr[store]=tmp;

return store;
}

var qsort = function(arr, begin, end)
{
if(end-1>begin) {
var pivot=begin+Math.floor(Math.random()*(end-begin));

pivot=partition(arr, begin, end, pivot);

qsort(arr, begin, pivot);
qsort(arr, pivot+1, end);
}
}

qsort(arr, 0, arr.length);
return null;
};

[Scott Graham]

On Wed, Jan 18, 2012 at 7:43 AM, Sphaerica <blac...@comcast.net> wrote:

Hi, thanks for taking a look.

Where did you get the in-place mergesort algorithm you used?

I don't recall, perhaps I made it up and that's why it's broken. :/ Otherwise, I would guess Wikipedia offhand.

 

Everything I've seen says such algorithms are complex and sometimes
expensive.

I may just replace yours with a regular mergesort, or a quicksort.

I think it can't be quicksort because python guarantees the sort to be stable.