JavaScript QuickSort Objects

Question

Assuming I have the following Javascript structure:

[
  {
    "hash": "fe5642d26d04cc7e7d47daa426da2a79e244bdcbae1594a12578f0d6fe03082e",
    "path": "/Users/justin/test/node-w.tar.gz"
  },
  {
    "hash": "b1adffc1988b7339c7d4c59310fb3a64ce89e776a4924d492e819a08a7dce3fd",
    "path": "/Users/justin/test/level-1/level-1-1/music.mp3"
  },
  {
    "hash": "fe5642d26d04cc7e7d47daa426da2a79e244bdcbae1594a12578f0d6fe03082e",
    "path": "/Users/justin/test/level-1/level-1-1/node-z.tar.gz"
  },
  {
    "hash": "2e456c8de66a4ab6cf929d52bd6928b2d0096a8116891ade3dde9588c5f6b3c2",
    "path": "/Users/justin/test/logo_large.psd"
  },
  {
    "hash": "fe5642d26d04cc7e7d47daa426da2a79e244bdcbae1594a12578f0d6fe03082e",
    "path": "/Users/justin/test/level-1/node-y.tar.gz"
  },
  {
    "hash": "fce57d4407e847c4c13cb2867d3f00f2aed4b5c569385d04765abe2fcae726bb",
    "path": "/Users/justin/test/level-1/install.dmg"
  }
]

This is just a basic example, in reality, its going to be thousands, even tens of thousands of objects long. I want to group the duplicates on hash, so basically sort by hash the fastest way possible, so quick sort. The result, then should look like:

[
  {
    "hash": "2e456c8de66a4ab6cf929d52bd6928b2d0096a8116891ade3dde9588c5f6b3c2",
    "path": "/Users/justin/test/logo_large.psd"
  },
  {
    "hash": "b1adffc1988b7339c7d4c59310fb3a64ce89e776a4924d492e819a08a7dce3fd",
    "path": "/Users/justin/test/level-1/level-1-1/music.mp3"
  },
  {
    "hash": "fce57d4407e847c4c13cb2867d3f00f2aed4b5c569385d04765abe2fcae726bb",
    "path": "/Users/justin/test/level-1/install.dmg"
  }, 
  {
     "hash": "fe5642d26d04cc7e7d47daa426da2a79e244bdcbae1594a12578f0d6fe03082e",
     "path": "/Users/justin/test/node-w.tar.gz"
   },
   {
     "hash": "fe5642d26d04cc7e7d47daa426da2a79e244bdcbae1594a12578f0d6fe03082e",
     "path": "/Users/justin/test/level-1/level-1-1/node-z.tar.gz"
   },
   {
     "hash": "fe5642d26d04cc7e7d47daa426da2a79e244bdcbae1594a12578f0d6fe03082e",
     "path": "/Users/justin/test/level-1/node-y.tar.gz"
   }
 ]

nrabinowitz · Accepted Answer · 2011-11-28 05:40:21Z

3

The standard Javascript Array.sort() is pretty fast:

myArray.sort(function(a,b) { 
    return a.hash == b.hash ? 0 : 
        a.hash > b.hash ? 1 : -1; 
});

Edit: As @Aaron notes, this is cleaner with .localeCompare:

myArray.sort(function(a,b) { 
    return a.hash.localeCompare(b.hash);
});

If you're just trying to find or group by duplicate hashes, though, you might want to collect in an object keyed to the hash:

var hashes = {},
    groups = [],
    i, hash;
for (i=0; i < myArray.length; i++) {
    hash = myArray[i].hash;
    if (hash in hashes) {
        hashes[hash].push(myArray[i]);
    } else {
        hashes[hash] = [myArray[i]];
    }
}
// now turn into an array
for (hash in hashes) {
    if (hashes.hasOwnProperty(hash)) {
        groups.push(hashes[hash]);
    }
}

The groups array would now have a series of 1-to-n length arrays, each containing all objects with a particular hash.

edited Nov 28, 2011 at 5:40

answered Nov 28, 2011 at 5:33

nrabinowitz

55.7k10 gold badges152 silver badges169 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Aaron Dufour Over a year ago

I would use the builtin string.stringCompare or string.localeCompare rather than rolling your own in an ugly pair of ternaries.

nrabinowitz Over a year ago

@AaronDufour - Thanks, didn't know about that method. Though I thought my ternaries were pretty :).

Aaron Dufour Over a year ago

I think a single ternary is pretty, but nested ones w/o parens scare me.

Collectives™ on Stack Overflow

JavaScript QuickSort Objects

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related