Слияние массивов с константной памятью
Как слить два отсортированных массива так, чтобы результат в итоге был в них самих? Первая часть - в первом, вторая - во втором. Эффективно.
Пример входных и выходных данных
{1 3 4}, {1 2 5} => {1 1 2}, {3 4 5}
Ответы (2 шт):
Первая шляпа:
kuku, массивы в памяти как правило занимают непрерывный участок памяти, поэтому к каждому элементу которого можно обращаться по смещению. В случае двух массивов - чуть не так, и первый и второй массив - могут быть разнесены в памяти.
Вторая шляпа:
В C++ есть и перегрузка многих итераторов, и есть функции сортировок в стандартной библиотеке. Был бы один массив - вы бы не заморачивались! А вот в случае двух массивов - просто обеспечьте перегрузку индексного оператора, и опять же воспользуйтесь функции сортировки из стандартной библиотеки.
Да, я помню постановку задачи ... но и вы помните - у каждой "ячейки" массива есть свой адрес (скорее - адрес начала+смещение). А у вас есть перегрузки операторов взятия элемента по индексу (к примеру). И есть перегрузки взятия адреса, оло-ло-ло....
Ликбез окончен. Пишите свой код, если не получится - сообщество направит.
Пишите fake-class, который умеет ссылаться на ячейки двух массивов, читать их и писать по индексу. А стандартная либа их быстр разбросает.
Третья шляпа:
Применить алгоритм сортировки. Учитывая размерности 2- массивов. Опять - же поиск индекса, откуда что считать.
Вам попалась сложная задача. Слияние без дополнительной памяти позволяет создать стабильную сортировку без дополнительной памяти.
Одна из стабильных сортировок - сортировка слиянием. Ключевая операция в ней - слияние двух отсортированных массивов в один с использованием дополнительного буфера. Если придумать как это сделать без буфера вы получите стабильную сортировку без дополнительной памяти. Подробности тут: Устойчивая_сортировка#Алгоритмы_сортировки_слиянием_без_дополнительной_памяти