How can I sort an array, yet exclude certain elements (to be kept at the same position in the array)

Question

This will be implemented in Javascript (jQuery) but I suppose the method could be used in any language.

I have an array of items and I need to perform a sort. However there are some items in the array that have to be kept in the same position (same index).

The array in question is build from a list of <li> elements and I'm using .data() values attached to the list item as the value on which to sort.

What approach would be best here?

<ul id="fruit">
  <li class="stay">bananas</li>
  <li>oranges</li>
  <li>pears</li>
  <li>apples</li>
  <li class="stay">grapes</li>
  <li>pineapples</li>
</ul>

<script type="text/javascript">
    var sugarcontent = new Array('32','21','11','45','8','99');
    $('#fruit li').each(function(i,e){
       $(this).data('sugar',sugarcontent[i]);
    })
</script>

I want the list sorted with the following result...

<ul id="fruit">
      <li class="stay">bananas</li> <!-- score = 32 -->
      <li>pineapples</li> <!-- score = 99 -->
      <li>apples</li> <!-- score = 45 -->
      <li>oranges</li> <!-- score = 21 -->
      <li class="stay">grapes</li> <!-- score = 8 -->
      <li>pears</li> <!-- score = 11 -->
  </ul>

Thanks!

Answer 1

This won't work as Bevan pointed out, but I will leave it here for educational purposes:

$('#fruit li').sort(function(a, b) {
    return ($(a).hasClass('stay') || $(b).hasClass('stay'))
        ? 0 : (a.data('sugar') > b.data('sugar') ? 1 : -1);
}).appendTo('#fruit');

Note: You need to set the sugar data with 'sugar' as name argument:

.data('sugar', sugarcontent[i]);

Answer 2

You're correct in thinking that the solution is generic and applicable to any development environment.

You'll need to partition your list of elements into two different lists - ones to be sorted, and ones to be left in place. Then, sort the first list and merge with the second.

The key problem you're facing is this: Most sort algorithms (including QuickSort, which is the most common one found in most frameworks) become quite ill-behaved if your comparison function relies on any external state (like item position).

Answer 3

This should do it:

var sugarcontent = new Array('32','21','11','45','8','99');
var list = $('#fruit');
var lis = list.find('li').each(function(i,e){
   $(this).data('score',sugarcontent[i]);
});
var stay = lis.filter('.stay').each(function(){
    $(this).data('index',$(this).index());
});
lis.sort(function(a,b){
    return $(b).data('score') - $(a).data('score');
}).appendTo(list);
stay.each(function(){
    var index = $(this).data('index');
    if (index == 0) {
        list.prepend(this);
    } else {
        lis.filter(':eq('+index+')').insertAfter(this);
    }
}

This caches the index of the items with the class stay and then it does the sort by score and then replaces the items with the class stay back in the correct place.

Answer 4

Algorithm is:

• Extract and sort items not marked with stay

• Merge stay items and sorted items

  var sugarcontent = new Array(32, 21, 11, 45, 8, 99);
  
  
  var items = $('#fruit li');
  
  
  items.each(function (i) {
      $(this).data('sugar', sugarcontent[i]);
      // Show sugar amount in each item text - for debugging purposes
      if ($(this).hasClass('stay'))
          $(this).text("s " + $(this).text());
      else
          $(this).text(sugarcontent[i] + " " + $(this).text());
  });
  
  
  // Sort sortable items
  var sorted = $(items).filter(':not(.stay)').sort(function (l, r) {
      return $(l).data('sugar') - $(r).data('sugar');
  });
  
  
  // Merge stay items and sorted items
  var result = [];
  var sortedIndex = 0;
  
  
  for (var i = 0; i < items.length; i++)
      if (!$(items[i]).hasClass('stay')) {
          result.push(sorted[sortedIndex]);
          sortedIndex++;
      }
      else
          result.push(items[i]);
  
  
  // Show result
  $('#fruit').append(result);