Как сделать функцию сортировки для решения этой проблемы?

Question

У меня есть массив объектов. Каждый объект содержит имя и свойство user_id.

const queue = [
  {
    user: 1,
    song: "Song1",
  },
  {
    user: 1,
    song: "Song2",
  },
  {
    user: 2,
    song: "Song3",
  },
  {
    user: 1,
    song: "Song4",
  },
  {
    user: 3,
    song: "Song5",
  },
];

Я бы хотел отсортировать его так, чтобы он выглядел следующим образом

const queue = [
  {
    user: 1,
    song: "Song1",
  },
  {
    user: 2,
    song: "Song3",
  },
  {
    user: 3,
    song: "Song5",
  },
  {
    user: 1,
    song: "Song2",
  },

  {
    user: 1,
    song: "Song4",
  },

];

Итак. Если пользователь 1 добавляет 10 песен в очередь, пользователь 2 добавляет 1 песню в очередь, а пользователь 3 добавляет 3 песни в очередь, очередь будет выглядеть следующим образом: user_1_entry,user_2_entry,user_3_entry,user_1_entry,user_3_entry,user_1_entry, user_3_entry, user_1_entry [...]

Как мне решить эту проблему?

Answer 1

Fast and less iteration. Группируйте элемент на основе пользователя и собирайте песню по одному от всех пользователей

    const queue = [
      { user: 1, song: "Song1" },
      { user: 1, song: "Song2" },
      { user: 2, song: "Song3" },
      { user: 1, song: "Song4" },
      { user: 3, song: "Song5" },
    ];
    const mapper = (data) => {
      return data.reduce((m, i) => {
        if (!m[i.user]) m[i.user] = [];
        m[i.user].push(i);
        return m;
      }, []);
    };
    const collect = (queue) => {
      const mappedData = mapper(queue);
      let result = [],
        counter = 0,
        row = 0;
      while (counter < queue.length) {
        if (mappedData[row] && mappedData[row].length) {
          const d = mappedData[row].shift();
          result.push(d);
          counter++;
        }
        row++;
        if (row === mappedData.length) row = 0;
      }
      return result;
    };
    console.log(collect(queue));
    // chunkSort(queue);

Answer 2

Вы можете использовать сортировку с картой , используя временный объект с хеш-таблицей для того же массива группы. Возьмите длину используемого массива в качестве группы для сортировки.

Сортировка происходит с группой и индексом.

Результат сопоставляется с индексом отсортированного временного массива.

const
    queue = [{ user: 1, song: "Song1" }, { user: 1, song: "Song2" }, { user: 2, song: "Song3" }, { user: 1, song: "Song4" }, { user: 3, song: "Song5" }],
    groups = Object.create(null),
    result = queue
        .map(({ user }, index) => ({ index, group: groups[user] = (groups[user] || 0) + 1 }))
        .sort((a, b) => a.group - b.group || a.index - b.index)
        .map(({ index }) => queue[index]);

console.log(result);

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