История изменений
Исправление quiet_readonly, (текущая версия) :
Обе задачи выполняются за 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, :
Обе задачи выполняются за O(n) для каждой сортировки достаточно просто
- в первом случае просто держать два индекса в массивах A и B да заполнять C, сравнивая элементы A.at(a) и B.at(b), выбирая меньший, увеличивая соответствующий индекс. Не забыть про копирование другого массива, когда один из них опустеет.
- во втором достаточно найти новую позицию (допустим она окажется правее) и сдвинуть элементы между старой и новой позициями на 1 влево, а сам элемент на нужную позицию вправо.
Если во втором случае даже O(n) не устраивает, то можно попробовать искать новый индекс за O(log(N)) бинарным поиском, а сам массив хранить в виде linked list, где перемещение элемента на новый индекс не требует сдвигов, а только перелинковки в двух местах.
Исходная версия quiet_readonly, :
Обе задачи выполняются за O(n) для каждой сортировки достаточно просто
- в первом случае просто держать два индекса в массивах A и B да заполнять C, сравнивая элементы A[a] и B, выбирая меньший, увеличивая соответствующий индекс. Не забыть про копирование другого массива, когда один из них опустеет.
- во втором достаточно найти новую позицию (допустим она окажется правее) и сдвинуть элементы между старой и новой позициями на 1 влево, а сам элемент на нужную позицию вправо.
Если во втором случае даже O(n) не устраивает, то можно попробовать искать новый индекс за O(log(N)) бинарным поиском, а сам массив хранить в виде linked list, где перемещение элемента на новый индекс не требует сдвигов, а только перелинковки в двух местах.