current community

your communities

more stack exchange communities

Stack Exchange
tour help
careers 2.0
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 0 down vote favorite

THIS QUESTION STILL HAS NOT BEEN CORRECTED ANSWERED AS OF Monday Oct 31 (People are wrongly answer it as if I'm asking for array.sort to be modified but I'm not asking that)

How do I override the built in JavaScript sort method for a single array (not Array.sort) with the radix-msd algorthim?

I have the algorithm for the radix msd sort, it's

// radix most-significant-bit sort for integers
//arr: array to be sorted
//begin: 0
//end: length of array
//bit: maximum number of bits required to represent numbers in arr
function radixsort (arr, begin, end, bit) {
    var i, j, mask;
    i = begin;
    j = end;
    mask = 1 << bit;
    while(i < j) {
        while(i < j && !(arr[i] & mask)) {
            ++i;
        }
        while(i < j && (arr[j - 1] & mask)) {
            --j;
        }
        if(i < j) {
            j--;
            var tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
        }
    }
    if(bit && i > begin) {
        radixsort(arr, begin, i, bit - 1);   //    <=== RECURSIVE FUNCTION
    }
    if(bit && i < end) {
        radixsort(arr, i, end, bit - 1);     //    <=== RECURSIVE FUNCTION
    }
}

And my JavaScript object array is:

homes[0].price;
homes[0].address;
homes[0].city;
homes[0].state;
homes[0].zip;

So that, when I call "homes.sort()" - I want it to sort the entire homes[x] array based on the price using my radix sort array from above. How do I do that?

share|improve this question

4 Answers 4

up vote 1 down vote accepted

I think modifying Array.prototype.sort is very dangerous (because all other codes probably using sort() will be affected). Here's the code though:

//Just use this function like radixsort(homes,0,homes.length,32)
function radixsort (arr, begin, end, bit) {
    var i, j, mask;
    i = begin;
    j = end;
    mask = 1 << bit;
    while(i < j) {
        while(i < j && !(arr[i].price & mask)) {
            ++i;
        }
        while(i < j && (arr[j - 1].price & mask)) {
            --j;
        }
        if(i < j) {
            j--;
            var tmp = arr[i].price;
            arr[i].price = arr[j].price;
            arr[j].price = tmp;
            i++;
        }
    }
    if(bit && i > begin) {
        radixsort(arr, begin, i, bit - 1);
    }
    if(bit && i < end) {
        radixsort(arr, i, end, bit - 1);
    }
}
//If you really want to modify default sort function:
Array.prototype.sort = function(){
    radixsort(this,0,this.length,32); //Use 'this' to access (get reference) to the array.
}
share|improve this answer
    
But if I did the top example, how would radixsort know to sort on the Price attribute of my array? I see you made the function assume the Price attribute existed in the array but I'd like to generalize the radixsort function to not assume the Price attribute. –  nickb Oct 31 '11 at 4:51
    
Actually the OP never claimed to want to override Array.prototype.sort (that would obviously be dangerous and foolish as you say!) -- they just wanted to use the homes.sort() syntax. By using the term "override" I think the OP made clear the desire to use a sort method just for the homes array and not to change the behavior for all arrays. –  Ray Toal Oct 31 '11 at 5:19
    
@RayToal, you are correct. –  nickb Oct 31 '11 at 5:21
    
@JiminP (or ANYONE), if you can help me generalize this so that I don't have to hardcode "Price" into the radix sort function, I'll make this answer correct/accepted. See my comment above. –  nickb Oct 31 '11 at 5:24
up vote 4 down vote

You don't need to override the sort function, you simply need to pass your comparer function to the sort method as a parameter.

The function signature for the parameter is function (a, b) where a is the item being compared to b.

If you need a different implementation of sort, set it as a different function rather than overriding the default behavior. You can do this for all arrays using:

Array.prototype.radixsort = function ( ...params... )

Which will allow you to call

[1,2,3].radixsort(...params...);

Alternatively, you can add a utility function to Array:

Array.radixsort = function ( ...params... )

Which will be called as:

Array.radixsort([1,2,3], ...params...);
share|improve this answer
    
I'm not looking to overload/override Array.sort, just Homes.sort –  nickb Oct 31 '11 at 5:28
    
N/A - This answer doesn't apply since I'm not looking to override Array.sort. Only homes.sort (unless advised else wise). –  nickb Oct 31 '11 at 5:36
up vote 0 down vote

Expanding on Ray Toal's and zzzzBov's discussion:

  function defaultCompare(a, b) {
      var a_str = str(a);
      var b_str = str(b);
      if (a_str < b_str) {
          return -1;
      } else if (a_str > b_str) {
          return 1;
      } else {
          return 0;
      }
   }

   homes.sort = function (compare_func) {
       compare_func = compare_func || defaultCompare;
       RadixSort(this, 0, this.length, 64);
   }

There are probably typos in the above, but it should be a step toward a more complete implementation.

share|improve this answer
up vote -1 down vote

First, since you will have an array of objects, you will need to modify your radix sort so that it examines not just the contents of the array slots themselves (which are objects) but rather just the price fields. So wherever you see 

arr[x]

for arbitrary x, you would instead use

arr[x].price

or if you feel like you might want to sort of other fields, generalize to

arr[x][field]

where field is a variable you can set to a field name.

Second, you say you want to use the syntax homes.sort(). While not recommended in practice, it's interesting to see how JavaScript does this "overriding" thing which under classical inheritance is very straightforward. To do this, you need to assign the right function to the sort property of homes. If the object referenced by the variable homes is the only object for which you want to sort like this, you can assign your function to homes like this:

homes.sort = function () {radixSort(homes, 0. homes.length, bit);}

I'm not sure what the value of bit needs to be. As this is a radix sort you need to be very careful with the way you represent prices, I think. Are all values positive?

Interesting question from a technical standpoint. "Overriding" under prototypal inheritance does occur (the most common example is toString) and can be done either by adding overrides to specific objects or by inserting new objects into the prototyp chain. In practice though, this is total overkill for your example. As you are sorting on simple fields, use a comparator and the standard Array.prototype.sort. Especially in the case of price, radix sorts are not very good for floating point values.

share|improve this answer
1  
don't override default functions with new behavior, it will cause massive headaches for future debugging. –  zzzzBov Oct 31 '11 at 4:51
    
@zzzzBov I'm inclined to agree with you for sort, but I wouldn't take that as general advice because the default function toString is ridiculous and meant to be overridden. :) I know what you mean though. Still, the question has merit from a technical standpoint, so I edited the answer to address your concern. –  Ray Toal Oct 31 '11 at 5:13
    
toString and valueOf are special cases that are used as a common interface to all objects, and are expected to have values overridden. You have to maintain that common interface for them to work correctly. You wouldn't return an object or number from toString, so if you're going to override sort, you'd have to make it work with the existing interface, which involves the first parameter being a comparer function. –  zzzzBov Oct 31 '11 at 14:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.