0
\$\begingroup\$

I was asked to create a jQuery plugin that would sort homogeneous DOM elements in a given DOM container element.

I came up with the idea to attach data-priority attribute to the elements that are to be sorted, e.g.:

<div class="offer-item" data-priority="10">..</div>

, and later use that attribute in a jQuery plugin.

The algorithm that I came up with works like this:

  1. Iterate over all elements that are to be sorted to find the element with the highest data-priority;
  2. Append that element to the container;
  3. Iterate over the remaining elements of the collection and find the element with the highest data-priority;
  4. Append the element to the container;
  5. ...continue like this recursively until the collection of elements is empty.

My plugin is initiated like this: $('.col-sm-6').sortItemsInContainer('.offer-item'); (it essentially says "sort all .offer-item items in .col-sm-6 container").

This is the code:

(function($) {
    $.fn.sortItemsInContainer = function(itemsSelector) {

        // Recursively sort DOM elements - highest priority on top
        var positionElements = function($items, $container) {
            if (0 === $items.length) {
                return;
            }
            var $highestEle = findHighestElement($items);

            $container.append($highestEle);
            $items = $items.not($highestEle);

            return positionElements($items, $container); // Recursive call

        };

        // Find DOM element with highest priority
        var findHighestElement = function($items) {

            var firstItem = $items.get(0);
            var $highest = $(firstItem);

            $.each($items, function() {
                var $current = $(this);
                if ($current.data('priority') > $highest.data('priority')) {
                    $highest = $current;
                }
            });

            return $highest;
        };

        return this.each(function() {
            var $container = $(this);
            var $itemsToSort = $container.children(itemsSelector);
            positionElements($itemsToSort, $container);
        });
    };
})(jQuery);

Now my questions are:

  1. Is my algorithm is optimal in terms of performance, or is it just terrible?
  2. Is there any other obvious and substantially more efficient way to accomplish this?

and lastly,

  1. I'd like to create some automated tests for this feature. Is this code testable? What would be the best way/technology to use in order to test it?
\$\endgroup\$
  • \$\begingroup\$ not optimal, not even close: you should be using javascript's inbuilt sort(), \$\endgroup\$ – Jasen Feb 8 '16 at 1:53
1
\$\begingroup\$

Your code is nice and easy to understand. I'm going to break my review down into two sections: in the first section, I will suggest a different implementation, and in the second section, I will answer your questions.


New solution

In case you were not aware, JavaScript has a built-in function for sorting lists: Array.prototype.sort.

This function, basically, is used to take a list of data and sort it based on either it's built-in function, or a simple function you provide. This function takes two items from the array and returns either 1, 0, or -1 to tell sort how to place them in the array (the original array is mutated).

So, that being said, a much simpler way to sort these elements would be to do this:

// Sorts the items from greatest to least priority
$items.sort(function(a, b) {
    var aPriority = a.data("priority");
    var bPriority = b.data("priority");

    if(aPriority > bPriority) {
        // Note this is -1 despite aPriority being greater; -1 moves aPriority earlier in the list, sorting it greatest to least
        return -1;
    }
    if(aPriority < bPriority) {
        return 1;
    }
    return 0;
}

Not only is this simpler (and probably faster), it is also more idiomatic and easier to understand what is being done here.

Now that the native sort method is being used, there is no need for recursive placement. Just use a loop:

var positionElements = function($items, $container) {
    if (0 === $items.length) {
        return;
    }

    // ... $items sorting ...

    while($items.length > 0) {
        $container.append($items[0]); // sorted greatest to least
        $items = $items.not($items[0]);
    }
};

This is much simpler now, and is a bit faster now that there is no recursion because there is only two places where the call stack is touched, rather than two places for every item in the list.


Questions

Is my algorithm is optimal in terms of performance, or is it just terrible?

There are a few places where this code is not quite optimal. Look at this flowchart of your code:

  1. Iterate through entire list to find highest element
  2. Place that element and remove it from the list.
  3. Go to 1 until list is empty.

It's not very efficient to be iterating through the entire list every time as long as there are still elements inside it. If, for example, there were 10 items in the list, the first you would iterate through 10 items, then 9 items, then 8 item... until you've iterated through 55 elements.

And that's why sorting the array first before working with it will be much faster (in fact, the highest voted question on Stack Overflow is about why processing a sorted array is faster).


I'd like to create some automated tests for this feature. Is this code testable? What would be the best way/technology to use in order to test it?

There are many unit testing frameworks out there. Honestly, I'm not that familiar with jQuery, so my suggestion may not actually be your best bet (although, the jQuery website does make a reference to a unit testing framework: QUnit).

A framework I would recommend is Cheerio. My main reason for this is because it allows to easily load HTML into a virtual DOM and perform any normal DOM operations on it. This means you could load some test components, run your sorting code on them, and use Cheerio to read the DOM and make sure they are properly sorted.

\$\endgroup\$
  • \$\begingroup\$ This is truly a thorough and very constructive answer. Thank you, sir. \$\endgroup\$ – luqo33 Feb 8 '16 at 19:32
1
\$\begingroup\$

Is my algorithm optimal in terms of performance, or is it just terrible?

Performance-wise, hard to tell. May not be so bad. Would need to run tests.

The worst feature is readability. It's not a standard approach to sorting.

Is there any other obvious and substantially more efficient way to accomplish this?

Yes.

  • Use javascript's native Array#sort() method, which is easy to apply because a jQuery collection is very simply converted to an array of elements. It's unlikely to be slower than the code in the question.
  • After sorting, loop through the sorted array and append the elements to container. They will then be in the desired order.
  • For flexibility/reuse, consider passing a sort callback as a parameter to the plugin and allow the caller to be in control.

Your plugin could be as simple as ...

(function($) {
    $.fn.sortItemsInContainer = function(itemsSelector, sortCallback) {
        return this.each(function() {
            var $container = $(this);
            $container.children(itemsSelector).get().sort(sortCallback).forEach(function(element, i) {
                $container.append(element);
            });
        });
    };
})(jQuery);

... which, to be equivalent to the code in the question, would be called something like :

$("myContainer").sortItemsInContainer('*', function(a, b) {
    var a_ = +a.getAttribute('data-priority');
    var b_ = +b.getAttribute('data-priority');
    return (a_ > b_) ? -1 : (a_ < b_) ? 1 : 0;
});

Demo

With some extra thought, you could maybe code a couple of built-in, named sorts in the plugin, or pass a callback for full flexibility.

Demo

I'd like to create some automated tests for this feature. Is this code testable? What would be the best way/technology to use in order to test it?

Automated tests would be fairly simple to code, though it's hard to envisage something flexible enough to handle any set of input elements.

It's maybe more realistic to prepare a few sets of test cases, each comprising input HTML (a container full of elements) and an array representing the expected sort order.

It would be a fairly minor challenge to run a sort and compare the resulting order of DOM elements with expectation.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the great suggestion about passing a custom callback! \$\endgroup\$ – luqo33 Feb 10 '16 at 10:30
  • \$\begingroup\$ I made a couple of edits and added a link to a demo. \$\endgroup\$ – Roamer-1888 Feb 10 '16 at 11:59
  • \$\begingroup\$ Thanks for the demo and further advice. How would you go about using pre-coded 'named sorts'. It'd be ideal if a user could use an alread-coded named sort OR pass any callback should they wish so. Also, for the testing part - some say that test cases should not manipulate DOM, but rather only logic should be tested so is is important to have the logic and DOM manipulation decoupled. However, in this particular case, I think the resulting state of DOM should be tested - would Jasmine be a good framework for such DOM-based testing ? \$\endgroup\$ – luqo33 Feb 18 '16 at 10:35
  • \$\begingroup\$ I added a link to show how you might achieve named sorts. \$\endgroup\$ – Roamer-1888 Feb 19 '16 at 15:52
  • 1
    \$\begingroup\$ The final product is far beyond my expectations. It's a pity I cannot upvote more. The named sorts is a great way to make this plugin versatile. \$\endgroup\$ – luqo33 Feb 20 '16 at 18:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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