Sorting an array in JavaScript using a reference array and swap function-CodePudding

I seem to have come across what's basically a leetcode question in some actual practical code I'm writing. My problem is that I need to sort an array using a reference array of indices and a swap function.

It may help to know the context of this problem. It's a simplified, isolated version of what I'm facing when trying to come up with a script to sort layers by object position within Adobe Illustrator via ExtendScript. That's why swapping is necessary, and that's why there's a reference array as opposed to just using the .sort() function.

The arrayToBeSorted contains the actual data that I'm trying to sort. The referenceArray is an already-sorted list of the indices of arrayToBeSorted. This referenceArray describes what order the items in the arrayToBeSorted should end up in, by referring the indices of the items in arrayToBeSorted.

Setup Example 1:

// index              0      1       2       3       4      5                   
arrayToBeSorted = [ "six", "four", "one", "three", "two", "five" ]
referenceArray  = [   2,     4,      3,      1,      5,     0    ]

function swapItems(a, b) {
    var temp = arrayToBeSorted[a];
    arrayToBeSorted[a] = arrayToBeSorted[b];
    arrayToBeSorted[b] = temp;
}

// desired outcome:
algorithmToSortArray(arrayToBeSorted, referenceArray)
// should return this: 
[
    "one",   // was arrayToBeSorted[2]
    "two",   // was arrayToBeSorted[4]
    "three", // was arrayToBeSorted[3]
    "four",  // was arrayToBeSorted[1]
    "five",  // was arrayToBeSorted[5]
    "six"    // was arrayToBeSorted[0]
]

Setup Example 2:

// index              0       1       2       3        4         5                   
arrayToBeSorted = [ "red", "green", "blue", "pink", "purple", "orange" ]
referenceArray  = [   5,      1,      4,      2,       0,        3     ]

function swapItems(a, b) {
    var temp = arrayToBeSorted[a];
    arrayToBeSorted[a] = arrayToBeSorted[b];
    arrayToBeSorted[b] = temp;
}

// desired outcome:
algorithmToSortArray(arrayToBeSorted, referenceArray)
// should return this: 
[
    "orange",  // was arrayToBeSorted[5]
    "green",   // was arrayToBeSorted[1]
    "purple",  // was arrayToBeSorted[4]
    "blue",    // was arrayToBeSorted[2]
    "red",     // was arrayToBeSorted[0]
    "pink"     // was arrayToBeSorted[3]
]

Solution constraints:

The solution should exclusively use the swap function to move items around in arrayToBeSorted in-place, and should preferably be optimized for the least number of swaps possible.

What would be the best way to write algorithmToSortArray()?

CodePudding user response：

This version is fairly simple:

const swap = (xs, i, j) => 
  [xs [j], xs [i]] = [xs [i], xs [j]]

const refSort = (vals, refs) => {
  const indices = Array .from (vals, (_, i) => i)
  refs .forEach ((r, i) => {
    const j = indices .indexOf (r)
    swap (indices, i, j)
    swap (vals, i, j)
  })
  return vals
}

console .log (
  refSort (["six", "four", "one", "three", "two", "five"], [2, 4, 3, 1, 5, 0])
)
console .log (
  refSort (["red", "green", "blue", "pink", "purple", "orange"], [5, 1, 4, 2, 0, 3])
)

.as-console-wrapper {max-height: 100% !important; top: 0}

We simultaneously re-sort the indices [0, 1, 2, ..., length] and our values by placing each of our references in place using swaps on both, based on the reference indices. There are n swaps, and if they are over-expensive, we can remove useless swaps with

  refs .forEach ((r, i) => {
    const j = indices .indexOf (r)
    if (i !== j) {
      swap (indices, i, j)
      swap (vals, i, j)
    }
  })

I think this would have to be minimal, although we do double-swaps everywhere.

This does no error-checking. If refs.length is different from vals.length, this would likely fail.

It's not clear to me if this simple approach will expand out to your real problem, but if not, it might serve as a basis for that. In that case, you might open a new question with a more real-world example. (Perhaps some changed values interspersed with others left alone, although I guess the fixed points above -- such as 'green' -- might be enough to demonstrate that it should work. It's just not clear to me.)

CodePudding user response：

I've come up with another solution that only use the swapItems method to update the arrayToBeSorted. I'm pretty sure it could be done simpler by storing individually the changement of position of each number instead of the swap per "loop" but it's getting late and this one work so i hope this helps you enough.

function algorithmToSortArray(arrayToBeSorted, referenceArray) {
    const changeHistory = []
    for(let i = 0; i < referenceArray.length; i  ) {
        number = referenceArray[i]

        for(let j = 0; j < changeHistory.length; j  ) {
            if(changeHistory[j][0] === number) {
                number = changeHistory[j][1]
            } else if (changeHistory[j][1] === number) {
                number = changeHistory[j][0]
            }
        }

        if (i !== number) {  // this avoid some unnecessary swaps
            swapItems(i, number)
        }
        changeHistory[i] = [i, number]
    }

    return arrayToBeSorted
}