jQuery sort by rating (desc) and hide divs based on value

Question

Hello,

I am trying to achieve the following. I have a dozen divs with something like:

    <div id=1><div>test 1</div><div>4</div></div>
<div id=2><div>test2</div><div>1</div></div>
<div id=3><div>test3</div><div>6</div></div>
<div id=4><div>test4</div><div>3</div></div>
<div id=5><div>test5</div><div>2</div></div>
<div id=6><div>test6</div><div>0</div></div>
<div id=7><div>test7</div><div>3</div></div>
 ...

Now I want to use jQuery to display only the top 5 divs i.e. the ones with rating 4,6,3,2,3 in that order and hide the rest.

Any idea how to go about this? I would prefer not to use any extra plugins etc.

Answer 1

Give your HTML more structure, so that you can use it with selectors:

<div class="song">
    <div>4</div>
</div>
<div class="song">
    <div>2</div>
</div>
<div class="song">
    <div>6</div>
</div>
<div class="song">
    <div>3</div>
</div>
<div class="song">
    <div>1</div>
</div>
<div class="song">
    <div>1</div>
</div>
<div class="song">
    <div>0</div>
</div>

O(n*logn)

allSongs = $("div.song").get();
allSongs.sort(function(a,b) {
    a = $(a);
    b = $(b);
    // calling a.text() does only work if there's no text besides the rating.
    if (a.text() > b.text()) {
        return -1;
    } else if (a.text() < b.text()) {
        return 1;
    } else {
        return 0;
    }
});

// hide all elements that have an index greater/equal to 5
$(allSongs.slice(5)).hide();

O(n*m)

songs = $("div.song").get();
for (var i = 0; i < 5; i++) {
    var indexOfTop = -1;
    var topRating = -1;
    // find best rated song
    jQuery.each(songs, function(j) {
        // this line needs to be adapted for your code
        var rating = $(this).text();
        if (rating > topRating) {
            topRating = rating;
            indexOfTop = j;
        }
    }); 
    // remove top item from array
    if (indexOfTop == -1) {
        // no items left in songs
        return false;
    } else {
        songs.splice(indexOfTop, 1);
    }
}

// remove remaining songs
$(songs).hide();

O(m*logn)

function BinaryHeap(keyFunction) { 
    if (arguments.length >= 1) { 
        this.keyFunction = keyFunction; 
    } 
    this.content = []; 
} 

BinaryHeap.buildHeap = function(items, keyFunction) { 
    var newHeap = new BinaryHeap(); 
    if (arguments.length >= 2) { 
        this.keyFunction = keyFunction; 
    } 
    // slice copies the array 
    newHeap.content = items.slice(0); 
    var firstParent = Math.floor((newHeap.content.length - 1) / 2); 
    for (var i = firstParent; i >= 0; i--) { 
        newHeap._siftDown(i); 
    } 
    return newHeap; 
} 

BinaryHeap.prototype = { 
    push: function(item) { 
        this.content.push(item) 
        this._siftUp(this.content.length - 1); 
    }, 
    pop: function() { 
        var value = this.content[0]; 
        var newHead = this.content.pop(); 
        if (this.content.length >= 1) { 
            this.content[0] = newHead; 
            this._siftDown(0); 
        } 

        return value; 
    }, 
    // default key function, it extracts a key from the object 
    keyFunction: function(a) { 
        return a; 
    }, 
    _siftDown: function(root) { 
        var length = this.content.length; 
        var k = 0; 
        while (root * 2 + 1 < length) { 
            k++; 
            var child = root * 2 + 1; 
            var rightChild = root * 2 + 2; 
            if (rightChild < length) { 
                child = this._max(child, rightChild); 
            } 

            if (this._max(root, child) == child) { 
                this._swap(root, child); 
            } else { 
                break; 
            } 
            root = child; 
        } 
    }, 
    _siftUp: function(child) { 
        while (child >= 0) { 
            var root = Math.floor((child - 1) / 2); 
            if (this._max(child, root) == root) { 
                this._swap(child, root); 
            } else { 
                return; 
            } 
            child = root; 
        } 
    }, 
    _max: function(a, b) { 
        return (this.keyFunction(this.content[a]) >= this.keyFunction(this.content[b])) ? a : b; 
    }, 
    _swap: function(a, b) { 
        var buffer = this.content[a]; 
        this.content[a] = this.content[b]; 
        this.content[b] = buffer; 
    } 
} 

allSongs = $("div.song"); 
// build heap in O(n) 
var myheap = BinaryHeap.buildHeap(allSongs.get(), function(item) { 
    return $(item).text(); 
}); 

// hide all items 
allSongs.hide(); 

// show top 5 
for (var i = 0; i < 5; i++) { 
    var item = myheap.pop(); 
    // less than 5 elements 
    if (typeof(item) == "undefined") 
        break; 
    $(item).show(); 
}

O(n)

Quite sure it's not possible.

Timed results

Results in Milliseconds
(Mac OS X 10.6, Safari 4.0.3, 2.4 Ghz Intel Core 2 Duo)
-------
10 elements
n*logn: 3
m*n: 2
m*logn: 2

100 elements
n*logn: 26
m*n: 11
m*logn: 5

1000 elements
n*logn: 505
m*n: 140
m*logn: 42

10000 elements
n*logn: 8016
m*n: 1648
m*logn: 442

Answer 2

Here is a quick hack I made up, so if it result's in death, I'm not liable...

var divs = $('div[id] div:contains("test") + div').get();

divs = divs.sort(function( a, b ) {
  return ( parseInt( b.textContent, 10 ) || -1 ) - ( parseInt( a.textContent, 10 ) || -1 );
}).slice(5);

$( divs ).hide();

But I agree that more HTML structure definitely makes your job easier...