5

This question deals with my algorithm and why it isn't working. More specifically, I would like to know how it can be improved to do what I want it to do. That is why it is different from the suggested duplicate question.

I am trying to create a function that sorts an array of objects based on a property value (int) that they all share in common, "indexFound". As you may suspect, I am trying to place elements with a lower indexFound at the beginning of the array.

function organizeTokens(list) {
    for (i = 0; i < list.length - 1; i++) {
        if (list[i].indexFound < list[i + 1].indexFound) {
          // do nothing
        } else if (list[i].indexFound > list[i + 1].indexFound) {
          var tempVal = list[i];
          list[i] = list[i + 1];
          list[i + 1] = tempVal;
        } else {
        // should not happen unless we are comparing the same token
        }
    }
};

As it stands, this code is not making any difference when I feed it an array of objects. The elements are still not in the order that they should be. Am I approaching this in the right way? Am I missing something obvious?

EDIT: -------------------------------------------------------------------

Example input: organizeTokens([{value: "if", indexFound: 7}, {value: "a", indexFound: 0}])

Expected output: [{value: "a", indexFound: 0}, {value: "if", indexFound: 7}]

Actual output: [{value: "if", indexFound: 7}, {value: "a", indexFound: 0}]

Streamer
  • 173
  • 1
  • 1
  • 11
  • 1
    Have you tried `Array.prototype.sort`? Or do you want to solve this problem algorithmically yourself? – Yeldar Kurmangaliyev Feb 28 '17 at 03:34
  • I haven't. I'll check the documentation now. I am looking for the most efficient, and ideally the simplest way possible to do this - as it is only a small cog in the giant machine that is the Lexer that I am building. – Streamer Feb 28 '17 at 03:36
  • Could you post an example of data for input, output expected and output you are really getting? – zer00ne Feb 28 '17 at 03:41
  • http://stackoverflow.com/questions/1129216/sort-array-of-objects-by-string-property-value-in-javascript - and it's the same with integers. – Matthew W. Feb 28 '17 at 03:41
  • Sure. @zer00ne Edited the post for you, check it out. – Streamer Feb 28 '17 at 03:44
  • Your algorithm looks like a single pass of a [bubble sort](https://en.wikipedia.org/wiki/Bubble_sort). Bubble sort requires `list.length` passes, not just one. – JLRishe Feb 28 '17 at 03:49
  • @JLRishe Increasing the amount of passes will result in the function attempting to access an index of an array that does not exist. – Streamer Feb 28 '17 at 03:53
  • @Azurasky Why would that result in it attempting to access an index that doesn't exist? Bubble sort involves `array.length` passes. That's how it works. – JLRishe Feb 28 '17 at 04:24

3 Answers3

23

You can use Array.prototype.sort() and define a compare function:

function compareIndexFound(a, b) {
  if (a.indexFound < b.indexFound) { return -1; }
  if (a.indexFound > b.indexFound) { return 1; }
  return 0;
}

list.sort(compareIndexFound);

Simpler/Concise version of above compare function:

function compareIndexFound(a, b) {
  return a.indexFound - b.indexFound;
}

Using ES6:

list.sort((a, b) => a.indexFound - b.indexFound);

You can define your own sortBy function:

function sortBy(arr, prop) {
  return arr.sort((a, b) => a[prop] - b[prop]);
}

sortBy(list, 'indexFound');
hackerrdave
  • 6,486
  • 1
  • 25
  • 29
  • In my context, how would I call this? Are a and b both equal to the same token List? Something like this?: list.sort(compareIndexFound(tokenList, tokenList))? – Streamer Feb 28 '17 at 03:59
  • Edit: Nevermind. I got it. Thanks for the help. This is much simpler than what I was trying to do. – Streamer Feb 28 '17 at 04:06
3

You can use JavaScript's built-in sort:

list.sort(function (l, r) {
    return l.indexFound - r.indexFound;
});

If you're using a utility like lodash or underscore, they have a sort function that's even simpler:

var sorted = _.sortBy(list, 'indexFound');

Example:

var list = [
    { indexFound: 9 },
    { indexFound: 3 },
    { indexFound: 17 },
    { indexFound: 1 }
];

var sorted = _.sortBy(list, 'indexFound');

console.log(sorted);
<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.4/lodash.min.js"></script>
JLRishe
  • 99,490
  • 19
  • 131
  • 169
0

Use the JS sort method with a custom callback function. Like this:

list.sort(function (a, b) {
    return a.indexFound - b.indexFound;
});

This will sort as ascending (lowest to highest).

Matthew W.
  • 413
  • 1
  • 9
  • 17