LINUX.ORG.RU

подскажите по сортировке

 ,


0

1

Здравствуйте. Подскажите какой алгоритм, сортировку использовать. Есть массив объектов. Каждый объект имеет бинарное состояние. Сначала надо вывести последовательно объекты с одним состоянием, потом с другим.( хотелось бы за один проход в цикле ). И если у какого то объекта меняется состояние, он попадает вниз списка объектов с таким же состоянием. Наведите плиз что эффективнее использовать, может сортировка существует подобная? А то как то в лоб у меня крайне неэффективно получилось сделать.

Всем заранее спасибо.



Последнее исправление: kabanchik (всего исправлений: 1)

Это называется priority queue (но там хитрости с произвольным доступом, если он тебе нужен).

Если у тебя гарантированно только два состояния, лучше сделать два разных массива/списка.

E ★★★
()
Ответ на: комментарий от E

Спасибо Вам. Произвольный доступ не нужен в принципе. А, например, какая структура данных еще может подойти для описанного случая, кроме как заиметь два разных массива?

kabanchik
() автор топика
Ответ на: комментарий от kabanchik

Навскидку не знаю. Если нужна мгновенная сортировка - однозначно древовидные структуры нужно брать, но это эквивалентно использованию priority queue.

Можно обойтись одним массивом и просто после каждого изменения состояния объекта «скатывать» его вниз, к товарищам. Для этого достаточно одного прохода, как первый анон сказал, O(n).

E ★★★
()
Ответ на: комментарий от E

Еще раз спасибо Вам, priority queue с двумя связанными списками наверное мне подойдет.

kabanchik
() автор топика

Определите функцию сравнения чтобы одно состояние было больше другого, потом можно использовать любую сортировку. Ну как вариант.

OxiD ★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.