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

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

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

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

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

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

Подскажите

Кнут подскажет.

Сайт Ильи Кантора, AlgoList

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

http://www.cyberforum.ru/cpp-beginners/thread27084.html