LINUX.ORG.RU
ФорумTalks

Подскажите подходящие алгоритмы сортировки

 


0

1
  1. Имеется несколько массивов разного размера (порядка 10000 элементов), типа double. Каждый массив упорядочен. Нужно их объединить в один большой массив, тоже упорядоченный. Скорость алгоритма имеет значение.
  2. Имеется один массив типа double (примерно 100 элементов). Сначала все элементы в нём инициализированы одним значением (скажем, 9000, симулирующим бесконечность). Затем в произвольном порядке элементы меняют свои значения. После каждого такого изменения нужно получить упорядоченный массив. Интересует максимально быстрый алгоритм, потому что такая операция повторяется столько раз, сколько всего элементов в массиве из первого пункта.

Заранее извиняюсь, если мой вопрос слишком ламерский, программирование не моя специальность, а гуглёж только запутал.

★★★★★

тебе нужно почитать про деревья.

Rastafarra ★★★★ ()

По поводу первого вопроса посмотрите как работает сортировка слиянием, а именно сам процесс слияния.

Второй вопрос не совсем понял, но, возможно, имеет смысл обратить внимание на структуру данных «очередь с приоритетом».

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

Второй вопрос не совсем понял

Переформулирую. Есть один массив типа double из 100 элементов. Сначала все элементы имеют значения 9000.0. Внезапно какой-то элемент в нём меняет значение на x < 9000.0. Сортируем массив (то есть помещаем элемент в начало). Затем ещё какой-то элемент меняет значение на y < 9000.0. Снова сортируем массив (изменённый элемент станет на вторую позицию, если y > x, или сдвинет первый элемент на вторую позицию, если y < x). И так далее.

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

А как будет использоваться отсортированный массив и для чего он нужен? Я предложил очередь с приоритетом, потому что она частично решает проблему «сортировки на каждый чих». Но она используется немного по-другому.

Изначально очередь пуста. В неё можно добавлять элементы по одному (например те, которые стали < 9000). И при этом вытаскивание наименьшего элемента из очереди происходит относительно быстро (быстрее, чем если бы делалась сортировка после каждого добавления). Однако вытащить например «второй по возрастанию» элемент не удастся, сначала надо вытащить первый.

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

Переформулирую. Есть один массив типа double из 100 элементов. Сначала все элементы имеют значения 9000.0. Внезапно какой-то элемент в нём меняет значение на x < 9000.0. Сортируем массив (то есть помещаем элемент в начало).

Не надо менять какой-то. Надо сразу выбирать подходящую позицию для элемента (это делается за O(log n)) и тогда массив всегда будет отсортирован.

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

После чего пододвинуть большие элементы за O(n)?

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

После чего пододвинуть большие элементы за O(n)?

А, да, массив же. Хотя если он достаточно разрежен, то это может оказаться быстрее, чем сортировка.

Relan ★★★★★ ()

Обе задачи выполняются за O(n) для каждой сортировки достаточно просто

  • в первом случае просто держать два индекса в массивах A и B да заполнять C, сравнивая элементы A.at(a) и B.at(b), выбирая меньший, увеличивая соответствующий индекс. Не забыть про копирование другого массива, когда один из них опустеет.
  • во втором достаточно найти новую позицию (допустим она окажется правее) и сдвинуть элементы между старой и новой позициями на 1 влево, а сам элемент на нужную позицию вправо.

Если во втором случае даже O(n) не устраивает, то можно попробовать искать новый индекс за O(log(N)) бинарным поиском, а сам массив хранить в виде linked list, где перемещение элемента на новый индекс не требует сдвигов, а только перелинковки в двух местах.

Только в linked list поиск элемента по индексу идёт за O(n), вроде бы можно улучшить, но как - не в курсе. Навскидку могу лишь предложить погуглить дерево отрезков и ropes.

quiet_readonly ★★★★ ()
Последнее исправление: quiet_readonly (всего исправлений: 2)
Ответ на: комментарий от CARS

очередь с приоритетом

Скорее уж heap и потом heap sort.

DELIRIUM ☆☆☆☆☆ ()

1. Тебе нужно попарно «слить» свои массивы друг с другом. http://ru.wikipedia.org/wiki/Сортировка_слиянием

2. Двигать элементы по массиву — не эффективно, лучше использовать сбалансированное дерево. Старое значение элемента из дерева удаляешь, новое значение в дерево вставляешь. Реализацию дерева лучше взять готовую, например std::multiset . Если бы тебе не нужно было всё время поддерживать массив в упорядоченном виде, то подошла бы такая штука: http://ru.wikipedia.org/wiki/Двоичная_куча

Manhunt ★★★★★ ()

man Дональд Кнут

Deleted ()
Ответ на: комментарий от eugeno

Переформулирую. Есть один массив типа double из 100 элементов. Сначала все элементы имеют значения 9000.0. Внезапно какой-то элемент в нём меняет значение на x < 9000.0. Сортируем массив (то есть помещаем элемент в начало). Затем ещё какой-то элемент меняет значение на y < 9000.0. Снова сортируем массив (изменённый элемент станет на вторую позицию, если y > x, или сдвинет первый элемент на вторую позицию, если y < x). И так далее.

По-моему, просятся извращения на тему пузырька/шейкера, ибо постановка задачи допускает очень важный чит.

yu-boot ★★ ()

1. Сортировка слиянием в чистов виде. Вернее тут сама сортировка не нужна, нужно только слияние.

2. Если нужно поддерживать массив постоянно упорядоченным, то тебе нужен heap (куча/пирамида в переводе).

snizovtsev ★★★★ ()

1. слияние - если есть память на копию то прекрасно , если сливать на месте ( то проблема очень сложная и смотри спец. литературу).

2. если тебе на каждом шаге нужно выдавать упорядоченый массив( что есть O(n)) то как не страно обычный сорт . т.е(хотя нет скорее скан вывод упорядоченого и вставка на положененое место всё это вместе снова будет O(n)- тока константа чуток больше)

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

а вообще твои 2 вопроса связаны

ибо модификация случайного элемента и получение вновь упорядоченого массива это посути слияние (упорядоченой последовательности с выпуском модивицированого элемента ) с последовательность состоящей из одного элемента по сути тут дополнительной памяти не нужно и если опятже необходимо на каждой модификации выдавать последовательность то линейный алго.

если же упорядоченость типо что после прекращения модификаций выдать как можно быстрее то ...

qulinxao ★★☆ ()

Всем спасибо за ответы, с первым действительно просто, во втором, скорее всего, мне нужен priority_queue.

eugeno ★★★★★ ()

кстати при модификации можно сравнивать со старым значением и если меньше то пузырёк вниз ( к началу) если больше то вврерх затем вывод

когда знаем что вврех можно сначала вывести левую затем в процесе перемещения пузырька верх выводим левую как оставили пузырёк наместе выводим остаток последовательности.

когда знаем что пузырёк вниз то выводим элементы последовательности пока пузырёк больше затем меняем местами пузырёк и текущий ( и так далее между новым и старым) затем вывод правой.

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

priority_queue не есть упорядоченая последовательность извлечение из очереди полной последовательности есть O(nlogn)

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

Я в начале не совсем правильно сформулировал, на самом деле в задаче мне нужен будет только наименьший элемент массива, и только когда он будет использован, тогда следующий. Вообще это очередь событий, в которой времена событий постоянно меняются, но всегда интересует только ближайшее событие.

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

приоритетная очередь вообще очень недооценена

кстати если нужно не 1-крайнее(максимальное/минимальное) - а например 10 крайнее - то тоже используем 2 приоритетные очереди как песочные часы где перешеек есть общая вершина двух очередей и одновременно 10 ( т.е сверху очередь на 9(не считая вершину) элементов, а внизу все остальные элементы)

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