sort a dictionary (or whatever key-value data structure in js) on word_number keys efficiently

Question

how do I sort a dictionary by key like

dict["word_21"] = "Hello Java";
dict["word_22"] = "Hello World";
dict["word_11"] = "Hello Javascript";

so that I get

dict["word_22"] = "Hello World";
dict["word_21"] = "Hello Java";
dict["word_11"] = "Hello Javascript";

There are word_number combinations on indices only and the values are strings. The indices are distinct (no equal values) but could be "undefined" in an error case

Edit: Actually I need the descending and ascending order of it. But the descending order is what I need at the moment.

Answer 1

A javascript object, here used as a key-value-map (called "dictionary"), has no order; ie. you can't sort it.

You would need an array for that, e.g.

[
    {id: "word_11", entry:"Hello Javascript"},
    {id: "word_21", entry:"Hello Java"},
    {id: "word_22", entry:"Hello World"},
]

then you could sort that by id or by entry. You might use your id-sort-algorithm for that.

---

Or you could use an array of your keys to sort, next to the unsorted data structure. This might be the best (efficient) and simplest approach:

var dict = {
    "word_21": "Hello Java",
    "word_22": "Hello World",
    "word_11": "Hello Javascript"
}; // init (like your example)

var keys = Object.keys(dict); // or loop over the object to get the array
// keys will be in any order
keys.sort(); // maybe use custom sort, to change direction use .reverse()
// keys now will be in wanted order

for (var i=0; i<keys.length; i++) { // now lets iterate in sort order
    var key = keys[i];
    var value = dict[key];
    /* do something with key & value here */
} 

Answer 2

Try this

var sorted = [];
for(var key in dict) {
    sorted[sorted.length] = key;
}
sorted.sort();

Sorting dict on its keys and writing it back to the object does not make sense to me, but here it goes:

function sortOnKeys(dict) {

    var sorted = [];
    for(var key in dict) {
        sorted[sorted.length] = key;
    }
    sorted.sort();

    var tempDict = {};
    for(var i = 0; i < sorted.length; i++) {
        tempDict[sorted[i]] = dict[sorted[i]];
    }

    return tempDict;
}

dict = sortOnKeys(dict);

Answer 3

If you just want to sort keys in an object, the following is fine (its a one liner)

/**
 * (typescript) returns the given object with keys sorted alphanumerically.
 * @param {T} obj the object to sort
 * @returns {T} the sorted object
 */
 const sort = <T extends object>(obj: T): T => Object.keys(obj).sort()
        .reduce((acc, c) => { acc[c] = obj[c]; return acc }, {}) as T

or the same in javascript

/**
 * (javascript) returns the given object with keys sorted alphanumerically.
 * @param {T} obj the object to sort
 * @returns {T} the sorted object
 */
 const sort = (obj) => Object.keys(obj).sort()
        .reduce((acc, c) => { acc[c] = obj[c]; return acc }, {})

Answer 4

@Amberlamps nice solution works most of the time. But, the OP is correct that there are splitting issues with certain keys. The default behavior of sort() in javascript is to use string Unicode code points to determine the order of the elements. For example, the following keys will not get sorted correctly using @Amberlamps method:

canvas_2_1/15/2018__2:55:20_PM

canvas_24_1/15/2018__2:55:20_PM

But we can customize the sort method taking advantage of the fact that sort() accepts an optional argument which is a function that compares 2 elements of the array.

By customizing the sort logic of the compare function and passing it to the sort() method the keys above get sorted correctly:

sorted.sort(function(a, b) {
    a = parseInt(get_between(a, 'canvas_', '_'));
    b = parseInt(get_between(b, 'canvas_', '_'));
    if (a > b) {
        return 1;
    }
    if (b > a) {
        return -1;
    }
    return 0;
    });

In this case I'm using the following get_between method:

function get_between(str, char_a, char_b) {
   res = str.split(char_a).pop().split(char_b).shift();
   return(res)
}

Th point is, if you have tricky keys (which may or may not be "proper" use of dict) you can adapt the sort function to still sort correctly.

Answer 5

Simply put, the dictionary type does not have a keys() method, while the Object type does. You can pass the Object.keys() method an iterable and get the keys back as a list which has a .sort() method.

Object.keys({r:2,d:2,c:3,p:0})
// returns ["r", "d", "c", "p"]
Object.keys({r:2,d:2,c:3,p:0}).sort()
// returns ["c", "d", "p", "r"]
Object.keys([6,7,8,9])
// returns ["0", "1", "2", "3"]

And finally, let's jsFiddle the OP's code.

Update: Bergi's answer had too much going on and I totally missed the "good answer" part. I didn't even notice he did the same thing I did in my jsFiddle.

Answer 6

To understand why it is not possible to sort a dictionary, we first need to understand how a dictionary works. Unlike a list which orders its items according to an index, a dictionary stores an item at a location indicated by the hash of its key. Using your example, the value "Hello Java" is stored at "word_21". This process involves using a mathematical function to turn "word_21" into a number that can be used as an address. The benefit to using hash-tables (another name for dictionaries) is that it is really efficient for finding values, because hashing a key is much easier than searching through every element of a list.

To recap, there is no way to reorder a dictionary like you are asking for. The only way to place a value before another value, i.e. changing it's location, is by changing its key. Its better to think of the order as arbitrary, and unpredictable.

While dictionaries are really helpful for quickly accessing values based on keys, you might consider using a different datatype for your situation. Why use numbered keys when you could much more easily use a list's index? If you are looking for a quick way to access dynamically changing values based on keys, use a dict. If you want to quickly access elements based on an index, and sorting, use a list. Although, nowadays you can find ordered dictionaries in most languages that also store the keys in an ordered list for indexing. In JS, I believe this still requires 3rd party libraries.

Answer 7

Came across this trying to remember my JavaScript syntax. This is how I solved it maybe it will help someone.

// Unsorted Dictionary
YourDict = {
"A" : "1"
"C" : "3"
"B" : "2"
};

// The object sorting function
let alphabetizeByKey = function (dict) {
   // Init your return object
   let retObj = {};

   // Pull keys into array and use builtin array sort to alphabetize
   let keys = Object.keys(dict).sort();

   // If you want descending add keys.reverse();

   // Now loop through your new alphabetical key array
   // Creating a new entry in your return object (dictionary)
   // And add the value from original dict based on the key
   keys.forEach(k => {
      retObj[k] = dict[k];
   });

   return retObj;
}

// You can pass it in and set it to the sorted value returned from the function
YourDict = alphabetizeByKey(YourDict)

This works because...

"A mutable value is one that can be changed without creating an entirely new value. In JavaScript, objects and arrays are mutable by default, but primitive values are not — once a primitive value is created, it cannot be changed, although the variable that holds it may be reassigned." -MDN