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

Question

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()?

Edited for spelling. I'm not using .sort() because this problem is an abstraction for sorting layers via scripting within an Adobe program, where .sort() wouldn't work. — boguslavsky
– boguslavsky, Commented Aug 15, 2022 at 1:24
Swapping is necessary because in the actual application of the solution, there would be other items between items in the array that would not be part of the sorting process, and would be ignored. However, those ignored items have to retain their place in the overall order. Not sure if that's clear... Essentially, this necessity for swapping is a result of this code working within Adobe Illustrator. It's a frustrating constraint. — boguslavsky
– boguslavsky, Commented Aug 15, 2022 at 1:37
Are you looking for something as simple as const result = referenceArray .map (i => arrayToBeSorted [i])? This does not swap in place, but maps; however it is quite simpler. — Scott Sauyet
– Scott Sauyet, Commented Aug 16, 2022 at 18:56

Scott Sauyet · Accepted Answer · 2022-08-17 14:27:13Z

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.)

Krayorn · Accepted Answer · 2022-08-16 22:46:09Z

1

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
}

edited Aug 16, 2022 at 22:46

answered Aug 16, 2022 at 9:37

Krayorn

958 bronze badges

2 Comments

boguslavsky Over a year ago

This doesn't work because it doesn't use the swap function on arrayToBeSorted. The initial array must be modified in-place using the swap function.

Krayorn Over a year ago

Hey @boguslavsky i've updated my answer with another solution, this should match what you need, hope this helps

Collectives™ on Stack Overflow

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

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related