Undo Sort On Sorted Array In Javascript

I have an array. I sort it. I get a second array which is already sorted based on the first one. I need to reverse the sorting on the second array. For example, if the first arra

Solution 1:

Storing res[i] = a - b is like journaling the sort() algorithm - but what if it used a random pivot? This code is inherently unreliable unless you write sort() yourself. It's also inefficient.

A better approach, one that will solve both your needs, is to create an array of indices and sort that. This is trivial to invert. Then you can implement a permute function that takes an array of indices, and it achieves a sort or unsort, depending on the input.

If x is from 0:n-1, create an array sort_i of same size, then initialize each sort_i[i] = i.

for(var i = 0; i < n; i++)
    sort_i[i] = i;

Then

sort_i.sort(function (a,b) { return x[a] - x[b]; });

Now you have the indices. To apply to x:

for(var i = 0; i < n; i++)
    sort_x[i] = x[sort_i[i]];

To unsort it, first invert the indices

for(var i = 0; i < n; i++)
    unsort_i[sort_i[i]] = i;

Then apply the indices. Exercise left to question asker.

This approach of sorting an array of integer indices is needed when you don't want to move the original elements around in memory (maybe they are big objects), and many other circumstances. Basically you are sorting pointers. The result is an index to the data, and a reverse index.

Solution 2:

See @duskwuff's answer on why your approach doesn't work.

Instead, just introduce a mapping between the original data and the sorted data.

{0:2, 1:3, 2:1, 3:0}

Which means the first element became the third, the second became the last and so on. Below we'll use an array instead of an object.

Why does this map help? You can sort it like another dataset by just using the indizes in it as pointers to the data you're going to compare. And you can apply the mapping easily on other datasets. And you can even reverse that mapping very easily. See it in the code:

// data_r, data_x are arrays with valuesvar l = data_r.length;
var sort_order = newArray(l);
for (var i=0; i<l; i++) sort_order[i] = i; // initialised as 1-1 mapping// change the sort_order first:
sort_order.sort(function (a,b) {
    // a and b being indicesreturn data_r[a] - data_r[b];
});

// Making a new, sorted arrayvar data_x_sorted = newArray(l);
for (var i=0; i<l; i++)
    data_x_sorted[ sort_order[i] ] = data_x[i]; // put it to sorted position

If you want to sort the data_x array itself, just use the "apply" algorithm which I showed for data_r.

The question is, how can I undo sort on the data_r array?

Either don't sort it at all, and just make a copy of it which gets sorted (or do nothing at all).

Or use the sort_order to reverse it. You just would need to swap i and newIndex (sortOrder[i]) everywhere. Example for building a new, "unsorted" (old-order) array:

var unsorted = newArray(l);
for (var i=0; i<l; i++)
    unsorted[i] = data_r[ sort_order[i] ]; // take it from its new position

Solution 3:

While this question is 8 years old at this point, I came across it when trying to find the same solution to the problem and I was unable to find a suitable, performant, and intuitive way of doing so, so I wrote one myself.

Please take a look at the sort-unwind library. If ranks is a list of indexes that would rank an array in order...

import unwind from'sort-unwind'const suits = ['♥', '♠', '♣', '♦']
const ranks = [2, 0, 3, 1]

const [sortedSuits, tenet] = unwind(ranks, suits)
// sortedSuits <- ['♠', '♦', '♥', '♣']// unwind <- [1, 3, 0, 2]

You can then use the tenet variable that's returned to unsort an array and restore the original ordering.

const names = ['spades', 'diamonds', 'hearts', 'clubs']
const [tenetNames, tenetRanks] = unwind(tenet, names)
// tenetNames <- ['hearts', 'spades', 'clubs', 'diamonds']// tenetRanks <- [2, 0, 3, 1]

Solution 4:

The sort function just returns a number which can be positive,zero, or negative telling it if the current element goes before,has same weight, or goes after the element it is comparing it too. I would imagine your sort order array is longer than your data_r array because of the number of comparisons you make. I would just make a copy of data_r before you sort it and then set data_r equal to that array when you want it unsorted.

Solution 5:

If you have a lot of these arrays to maintain, it might be as well to convert array1 into an array of objects, each one containing the value and its original position in the array. This keeps everything together in one array.

var array1 = [9, 5, 3, 0, 2];
var array2 = ["home", "car", "train", "pc", "mouse"];

var sort = function(array){
    var indexed_objects =  array.map(function(value, index){
        return {index: index, value: value};
    });
    indexed_objects.sort(function(a,b){
        return a.value <= b.value ? -1 : 1;
    });
    return indexed_objects;
};

var sorted1 = sort(array1);
sorted1; // [{index: 3, value:0}, {index: 4, value: 2}, ...]

And now, given an array of sorted objects, we can write a function to unsort any other array accordingly:

var unsort = function(array, sorted_objects){
    var unsorted = [];
    sorted_objects.forEach(function(item, index){
        unsorted[item.index] = array[index];
    });
    return unsorted;
};

var array2_unsorted = unsort(array2, sorted1);
array2_unsorted; // ["mouse", "pc", "train", "home", "car"]