PragmaGames
@PragmaGames
Увлекаюсь Unity.

Как лучше сортировать данные в которых не отсортирован только 1 объект?

Всем привет. Есть массив позиций объектов (Xpos, Ypos,Zpos), данный массив должен быть всегда отсортирован по возрастанию Ypos. В любой момент времени любой из объектов может поменять свою позицию, мы знаем что это за объект. После каждого изменения массив нужно сортировать, каким способом лучше это сделать ? Либо возможно вообще стоит использовать двусвязный список и если объект меняется удаляем его из списка и вставляем в нужную позицию ?
  • Вопрос задан
  • 94 просмотра
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Нужно делать вставку, как в insert sort. Вы написали, что используете бинпоиск в этом массиве, поэтому реализовывать его на связных списках нельзя. Поэтому у вас будет массив и вы за один проход сможете переместить элемент куда надо.

Самое быстрое - это обработать 2 случая, элемент изменил свое значение вниз или вверх. Потом циклом или влево или вправо надо swap-ать его со следующим, пока они стоят не в том порядке. Можно чуть соптимизировать и выкинуть лишние операции из каждого свап-а:
// a[moved] увеличился.
tmp = a[moved];
for (i = moved+1; i < a.size() && a[i] < tmp; ++i) {
  a[i-1] = a[i];
}
a[i-1] = tmp;
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы