Javascript Array Sorting Headache

Question

I have an array of objects that looks similar to this:

[
    {
        id : 1,
        position: false
    },
    {
        id: 2,
        position: false
    },
    {
        id: 3,
        position: 4
    },
    {
        id: 4,
        position: false
    },
    {
        id: 5,
        position: 2
    },
    {
        id: 6,
        position: 5
    },
    {
        id: 7,
        position: 3
    },
    {
        id: 8,
        position: 1
    },
]

I would like to sort this array using the position property (ascending) of each object so that the array looks like this:

[
    {
        id: 8,
        position: 1
    },
    {
        id: 5,
        position: 2
    },
    {
        id: 7,
        position: 3
    },
    {
        id: 3,
        position: 4
    },
    {
        id: 6,
        position: 5
    },
    {
        id: 1,
        position: false
    },
    {
        id: 2,
        position: false
    },
    {
        id: 4,
        position: false
    }
]

The idea is only to move the objects with a position that isnt false to the top without affecting the order of the rest of the objects with a position set to false.

Seems easy enough, right? I've tried to approach this problem in so many ways but nothing seems to work reliably. Hopefully someone can help me get my head around how to properly go about this.

Help me Stack Overflow, you're my only hope.

Answer 1

The easy way to sort your data would be to use the use the Array.sort() function. First check if the position of object 2 is false, if so return -1 to float object 1 to top. Do the opposite for object 1. If both are not false, do an integer compare.

var data = [
    { id: 1, position: false },
    { id: 2, position: false }, 
    { id: 3, position: 4 },
    { id: 4, position: false },
    { id: 5, position: 2 },
    { id: 6, position: 5 },
    { id: 7, position: 3 },
    { id: 8, position: 1 }
];

data.sort(function (a, b) {
    posa = a.position;
    posb = b.position;
    
    if (!posb) return -1;
    if (!posa) return 1;
    
    return posa - posb;
});

console.log(data);

But this solution may not be the best because Array.sort() does not require a standard according to ECMA International:

Excerpt below taken from ECMAScript Language Specification, 2011, p.129

15.4.4.11 Array.prototype.sort (comparefn)

The elements of this array are sorted. The sort is not necessarily stable (that is, elements that compare equal do not necessarily remain in their original order). If comparefn is not undefined, it should be a function that accepts two arguments x and y and returns a negative value if x < y, zero if x = y, or a positive value if x > y.

A work around for this would be for you to devise your own sorting algorithm. Preferably a merge or quick-sort algorithm. Below is an implementation of the quick-sort algorithm used to sort the data as intended. Note: There is a link to JSFiddle at the bottom of this response.

/**
 *  Add a swap function to the Array object.
 *  @param a Object a.
 *  @param b Object b.
 */
Array.prototype.swap = function (a, b) {
    var tmp = this[a];
    this[a] = this[b];
    this[b] = tmp;
};

/**
 *  A utility function to print out HTML to the screen in case the user's
 *  console is not enabled or present.
 *  @param message The message to print to the screen.
 */
var trace = function (message) {
    id = 'trace';
    t = $('#' + id);
    if (t.length < 1) t = $('<div>', {
        'id': id
    }).appendTo($('body'));
    t.append($('<p>', {
        'html': message
    }));
};

/**
 *  An implementation of the quick-sort algorithm that allows the user to
 *  use a custom comparator with the following signature
 *  {@code function(a, b) } which will return an integer value to determine
 *  ordering. 
 *  @param array The array to be sorted.
 *  @param comparator The custom comparator function.
 */
var quickSort = function (array, comparator) {
    var __internal_compare__ = function compare(a, b) {
        if (a < b) return -1;
        if (a > b) return 1;
        return 0;
    };
    
    comparator = comparator || __internal_compare__;
    
    var qsort = function (array, begin, end, comparator) {
        if (end - 1 > begin) {
            var pivot = begin + Math.floor(Math.random() * (end - begin));

            pivot = partition(array, begin, end, pivot, comparator);

            qsort(array, begin, pivot, comparator);
            qsort(array, pivot + 1, end, comparator);
        }
    };

    var partition = function (array, begin, end, pivot, comparator) {
        var piv = array[pivot];
        array.swap(pivot, end - 1);
        var store = begin;
        var ix;
        
        for (ix = begin; ix < end - 1; ++ix) {
            if (piv != undefined && comparator(piv, array[ix]) < 0) {
                array.swap(store, ix);
                ++store;
            }
        }
        
        array.swap(end - 1, store);

        return store;
    };

    qsort(array, 0, array.length, comparator);
};

// The custom compare function to be used on the array of data below
// in the quick-sort function.
var compare = function (a, b) {
    var isBoolAndFalse = function (val) {
        return typeof val === 'boolean' && !val;
    };

    if (a == b) return 0;

    var posa = a.position;
    var posb = b.position;
    var cona = isBoolAndFalse(posb);
    var conb = isBoolAndFalse(posa);

    if (cona && conb) {
        var ida = a.id;
        var idb = b.id;

        return idb - ida;
    }

    if (conb) return -1;
    if (cona) return 1;

    return posb - posa;
};

/**
 *  Main procedure follows:
 */

var data = [
    { id: 1, position: false },
    { id: 2, position: false }, 
    { id: 3, position: 4 },
    { id: 4, position: false },
    { id: 5, position: 2 },
    { id: 6, position: 5 },
    { id: 7, position: 3 },
    { id: 8, position: 1 }
];

quickSort(data, compare);

trace(JSON.stringify(data, undefined, 2));

Output:

[
  {
    "id": 8,
    "position": 1
  },
  {
    "id": 5,
    "position": 2
  },
  {
    "id": 7,
    "position": 3
  },
  {
    "id": 3,
    "position": 4
  },
  {
    "id": 6,
    "position": 5
  },
  {
    "id": 1,
    "position": false
  },
  {
    "id": 2,
    "position": false
  },
  {
    "id": 4,
    "position": false
  }
]

You can test the above code out by using the following JSFiddle Demo. I hope this clears thing up for you.

Answer 2

I tried to add a bunch of comments to help you follow my ideas. This is implemented in an imperative style, and (I hope) can help with illustrating some ideas for how to approach similar problems.

I used your sample data set, and reproduced the result you were looking for. I hope this is helpful and that it can be modified to suit whatever data you require.

I also pasted the text here.

var deepSort = function(arr){
  var i;
  var hasPositionKey = [];
  var noPositionKey = [];
  var nestedObj;
  var positions = [];
  var loggingPositions = {};
  var positionSortedObjects = [];

  // iterate through the array of objects
  for(i = 0; i < arr.length; i++){
    // set a variable for the individual object being considered
     nestedObj = arr[i];
    // if that object has a position of false
    if(nestedObj.position === false){
      // push false object into the array of false position objects
      noPositionKey.push(nestedObj);
    }
    // if the object has a numbered position
    if(typeof nestedObj.position === 'number'){
      // push numbered position to the array of numbered position objects
      hasPositionKey.push(nestedObj);
    }
  }

  // iterate through the array of objects with positions
  for(i = 0; i < hasPositionKey.length; i++){
    // set a variable for the individual object being considered
    nestedObj = hasPositionKey[i];
    // push only the position number into an array to track positions
    positions.push(nestedObj.position);
    // add a key value pair of position:id to an object
    loggingPositions[nestedObj.position] = nestedObj.id;
  }

  // sort the array that stores the positions of the non-false objects
  positions.sort();
  // iterate through that array and construct a final array of objects by sorted position
  for(i = 0; i < positions.length; i++){
    // set a variable for the positions, as encountered in order:
    var num = positions[i];
    // set a key for the object to be constructed
    var key = loggingPositions[num];
    // set a value for the object to be constructed
    var value = num;
    // construct a result object with object literal notation:
    var result = {
      id: key,
      position: value
    };
    // push the constructed objects into the positionSortedObjects array
    positionSortedObjects.push( result );
  }

  // return a concatenated array of the positionSortedObjects + the noPositionKey objects
  return (positionSortedObjects.concat(noPositionKey));  
};

var sample = [
    {
        id : 1,
        position: false
    },
    {
        id: 2,
        position: false
    },
    {
        id: 3,
        position: 4
    },
    {
        id: 4,
        position: false
    },
    {
        id: 5,
        position: 2
    },
    {
        id: 6,
        position: 5
    },
    {
        id: 7,
        position: 3
    },
    {
        id: 8,
        position: 1
    }
];

deepSort(sample);