Javascript sorting algorithm

Question

I need help applying a proper sorting algorithm for this. I'm trying to calculate a schedule for teams performing in a teamgym tournament.

The rules:

In short; the discipline.sortOrder must be in sequence (1), and one team should not perform in two consecutive disciplines (2).

(1) For each row in the array, the next sequence of discipline.sortOrder must be applied.

Example: If result[0].discipline.sortOrder === 0, then result[1].discipline.sortOrder === 1.

(2) Each row in the array must contain a different team than the previous row.

Example: If result[0].team.id === 1, then result[1].team.id !== 1

What I have so far

var schedule = [
  { "team":{"id": 1, "name": "Haugesund-1"}, "discipline":{ "name":"Frittstående", "sortOrder":0 } },
  { "team":{"id": 1, "name": "Haugesund-1"}, "discipline":{ "name":"Trampett",     "sortOrder":1 } },
  { "team":{"id": 1, "name": "Haugesund-1"}, "discipline":{ "name":"Tumbling",     "sortOrder":2 } },
  { "team":{"id": 2, "name": "Sola-1"},      "discipline":{ "name":"Frittstående", "sortOrder":0 } },
  { "team":{"id": 2, "name": "Sola-1"},      "discipline":{ "name":"Trampett",     "sortOrder":1 } },
  { "team":{"id": 2, "name": "Sola-1"},      "discipline":{ "name":"Tumbling",     "sortOrder":2 } },
  { "team":{"id": 3, "name": "Stavanger-1"}, "discipline":{ "name":"Frittstående", "sortOrder":0 } },
  { "team":{"id": 3, "name": "Stavanger-1"}, "discipline":{ "name":"Trampett",     "sortOrder":1 } },
  { "team":{"id": 3, "name": "Stavanger-1"}, "discipline":{ "name":"Tumbling",     "sortOrder":2 } },
  { "team":{"id": 4, "name": "Ålgård"},      "discipline":{ "name":"Frittstående", "sortOrder":0 } },
  { "team":{"id": 4, "name": "Ålgård"},      "discipline":{ "name":"Trampett",     "sortOrder":1 } },
  { "team":{"id": 4, "name": "Ålgård"},      "discipline":{ "name":"Tumbling",     "sortOrder":2 } }
];

var sorted = schedule.sort((a, b) => {
  // Sort by team (This is wrong!!)
  if (a.team.id != b.team.id) return a.team.id < b.team.id ? -1 : 1;

  // Sort by discipline
  const aDis = a.discipline.sortOrder;
  const bDis = b.discipline.sortOrder;
  if (aDis != bDis) { return aDis < bDis ? -1 : 1; }

  return 0;
});

// Write out result
document.querySelector('#result').innerText = sorted.map(s => JSON.stringify(s)).join('\n');

<h1>Result</h1>
<pre id="result"></pre>

I find it hard to dictate the order of things when b is not necessarily the next nor previous in sequence. This sort will create an order which is equal to the original. This is not the result I was looking for.

RESULT This is what I would like to end up with:

var result = [
  { "team":{"id": 1, "name": "Haugesund-1"}, "discipline":{ "name":"Frittstående", "sortOrder":0 } },
  { "team":{"id": 2, "name": "Sola-1"},      "discipline":{ "name":"Trampett",     "sortOrder":1 } },
  { "team":{"id": 3, "name": "Stavanger-1"}, "discipline":{ "name":"Tumbling",     "sortOrder":2 } },
  { "team":{"id": 2, "name": "Sola-1"},      "discipline":{ "name":"Frittstående", "sortOrder":0 } },
  { "team":{"id": 1, "name": "Haugesund-1"}, "discipline":{ "name":"Trampett",     "sortOrder":1 } },
  { "team":{"id": 4, "name": "Ålgård"},      "discipline":{ "name":"Tumbling",     "sortOrder":2 } },
  { "team":{"id": 3, "name": "Stavanger-1"}, "discipline":{ "name":"Frittstående", "sortOrder":0 } },
  { "team":{"id": 4, "name": "Ålgård"},      "discipline":{ "name":"Trampett",     "sortOrder":1 } },
  { "team":{"id": 1, "name": "Haugesund-1"}, "discipline":{ "name":"Tumbling",     "sortOrder":2 } },
  { "team":{"id": 4, "name": "Ålgård"},      "discipline":{ "name":"Frittstående", "sortOrder":0 } },
  { "team":{"id": 3, "name": "Stavanger-1"}, "discipline":{ "name":"Trampett",     "sortOrder":1 } },
  { "team":{"id": 2, "name": "Sola-1"},      "discipline":{ "name":"Tumbling",     "sortOrder":2 } }
]

Is this even possible to do using .sort?

What does *"and one team should not perform in two consecutive disciplines"* mean? Consecutive in what way? (This may *not* be covered by the other question's answers after all...) — T.J. Crowder, Apr 26 '17 at 07:24
@NinaScholz, I've removed the sequence from the array. I originally added them to illustrate the difference between the original array and the wanted result. — Øystein Amundsen, Apr 26 '17 at 07:47
@ØysteinAmundsen, the line number is not the problem, but `"Haugesund-1"`, for example, has no key. — Nina Scholz, Apr 26 '17 at 07:53
You are absolutely right @NinaScholz. My bad. I've simplified the array from the original data. The key got lost in the process. Thank you. — Øystein Amundsen, Apr 26 '17 at 07:56
It seems clear that this *cannot* be solved using `.sort` as it's impossible to compare any two given results and determine categorically which should come first; knowledge of the overall context would be required. — richsilv, Apr 26 '17 at 08:36
I am at liberty to add properties to the dataset as required, if that would help. If not, what would you propose @richsilv? A recursive forEach over the original array and push into a new array when rules above are met? — Øystein Amundsen, Apr 26 '17 at 08:39
@ØysteinAmundsen: Is the fact that sortOrder will be in the range 0, 1, 2 known in advance? Or could it be a broader range sometimes and narrower other times? — T.J. Crowder, Apr 26 '17 at 08:47
@T.J.Crowder The discipline.sortOrder **must** be in order (0,1,2) yes. But some teams compete in all disciplines, and some in only a few. So this could be both broader and narrower yes. — Øystein Amundsen, Apr 26 '17 at 08:50
@ØysteinAmundsen: So we might see `sortOrder` of 4, 6, 7? It's not always in the range 0-2? — T.J. Crowder, Apr 26 '17 at 09:03
@T.J.Crowder No, it is in patterns similar to [0,1,2] - [0, 2] - [1, 2] - [2] and so on. — Øystein Amundsen, Apr 26 '17 at 09:36

score 1 · Accepted Answer · answered Apr 26 '17 at 09:17

I don't think sort can do this.

This does it by starting with the first entry and then finding the next entry where the team number is higher and the sort order is next in order (wrapping to 2 back to 0).

If the range of sortOrder isn't always 0-2, you can find the max sortOrder in advance and then use that instead of 3 in the % 3.

In this example, I've removed team #1's Tumbling entry so we see that it works even if all teams don't have all sort orders.

const data = [
  { "team":{"id": 1, "name": "Haugesund-1"}, "discipline":{ "name":"Frittstående", "sortOrder":0 } },
  { "team":{"id": 1, "name": "Haugesund-1"}, "discipline":{ "name":"Trampett",     "sortOrder":1 } },
//  { "team":{"id": 1, "name": "Haugesund-1"}, "discipline":{ "name":"Tumbling",     "sortOrder":2 } },
  { "team":{"id": 2, "name": "Sola-1"},      "discipline":{ "name":"Frittstående", "sortOrder":0 } },
  { "team":{"id": 2, "name": "Sola-1"},      "discipline":{ "name":"Trampett",     "sortOrder":1 } },
  { "team":{"id": 2, "name": "Sola-1"},      "discipline":{ "name":"Tumbling",     "sortOrder":2 } },
  { "team":{"id": 3, "name": "Stavanger-1"}, "discipline":{ "name":"Frittstående", "sortOrder":0 } },
  { "team":{"id": 3, "name": "Stavanger-1"}, "discipline":{ "name":"Trampett",     "sortOrder":1 } },
  { "team":{"id": 3, "name": "Stavanger-1"}, "discipline":{ "name":"Tumbling",     "sortOrder":2 } },
  { "team":{"id": 4, "name": "Ålgård"},      "discipline":{ "name":"Frittstående", "sortOrder":0 } },
  { "team":{"id": 4, "name": "Ålgård"},      "discipline":{ "name":"Trampett",     "sortOrder":1 } },
  { "team":{"id": 4, "name": "Ålgård"},      "discipline":{ "name":"Tumbling",     "sortOrder":2 } }
];
const result = [];
let index = 0;
let entry = data[0];
while (data.length) {
    result.push(entry);
    data.splice(index, 1);
    index = data.findIndex(e => e.team.id > entry.team.id && e.discipline.sortOrder == ((entry.discipline.sortOrder + 1) % 3));
    index = index == -1 ? 0 : index;
    entry = data[index];
}
result.forEach(e => console.log(`team: ${e.team.id}, sortOrder: ${e.discipline.sortOrder}`));

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

Can't say I like how it has to repeatedly loop.

@ØysteinAmundsen: :-) Glad that helped. I suspect it *isn't* brilliant, I think there's a way with less looping, but I'm a bit out of it today and haven't come up with it. But unless the data is in the hundreds of thousands of recods, it doesn't really matter... — T.J. Crowder, Apr 26 '17 at 10:09

score 0 · Answer 2 · answered Apr 26 '17 at 09:34

There is an easy way to solve your problem if the array is valid (all team have exactly the same disciplines) and if we assume that it's initially sorted the way it looks in your question; if not a simple sort() could ensure that:

// Ensure that the array is initially sorted by teams and each team by discipline.sortOrder
schedule.sort((a, b) => (a.team.id == b.team.id) 
    ? a.discipline.sortOrder - b.discipline.sortOrder 
    : a.team.id - b.team.id
)

Then all you need now is loop over the array one time the following way:

// Loop wisely over the array and constructe the sorted one 
const disciplineCount = 3, // <- because in your example there are 0, 1 and 2
      size = schedule.length
let i = 0,
    step = 1,
    sorted = []

while (step <= size) {
    sorted.push(schedule[i])
    i = (step % disciplineCount == 0)
        ? i + 1
        : (i + disciplineCount + 1) % size
    step ++
}

Now sorted will contain your desired result.

Note that disciplineCount value should be dynamic depending on your array !

Hope this helps :D

*"if the array is valid (all team have exactly the same disciplines)"* The OP has said in the comments that that is not a valid assumption. I feel certain there *is* a way to do something like the above, but you'll have to remove that assumption from the code. — T.J. Crowder, Apr 26 '17 at 09:39
Recommend using a snippet to demonstrate any solution you come up with. — T.J. Crowder, Apr 26 '17 at 09:39

score -1 · Answer 3 · answered Apr 26 '17 at 09:04

I think this should work, but with constraints:

function sortResults (results) {
  const maxSortOrder = results.reduce((maxSoFar, { discipline: { sortOrder } }) => Math.max(maxSoFar, sortOrder), 0)

  const defaultTeam = { team: { id: '*****' }, discipline: { sortOrder: -1 } } // this is just to ensure a match the first time round
  const sortedResults = results.reduce(({ array, remaining, previous }) => {
    const nextSortOrder = (previous.discipline.sortOrder + 1) % (maxSortOrder + 1)
    const nextResultInd = remaining.findIndex(({ team: { id }, discipline: { sortOrder } }) => {
      return id !== previous.team.id && sortOrder === nextSortOrder
    })

    if (nextResultInd === -1) throw new Error('Result set cannot be sorted as required')

    previous = remaining.splice(nextResultInd, 1)[0]
    array.push(previous)

    return { array, remaining, previous }
  }, { array: [], remaining: results.slice(0), previous: defaultTeam })

  return sortedResults.array
}

It's inflexible in terms of sort order, so that if you've just had discipline 0 then you must have discipline 1 next, which if there's only one team to go and they only have discipline 2 still to do will result in an error when realistically you could just skip over discipline 1 in that case. However, I think it should be easy to relax this constraint based on your requirements, but I'll let you do that.

Perhaps explain *how* it works, and prove that it does with a working snippet? — T.J. Crowder, Apr 26 '17 at 09:13

Javascript sorting algorithm

3 Answers3