MS
На самом деле я готов использовать больше памяти, но так чтоб зааллоцировать её заблаговременно и во время сортировки ничего дополнительно аллоцировать не пришлось. Массивы одинаковой длины.
Size: a a a
2020 November 08
P
Йо! Я хочу отсортировать элементы одного массива согласно элементам другого массива. Как мне это сделать в О(1) памяти (инплейс)?
А что не так с обычной heap sort?
MS
Массивы которые нужно отсортировать раздельные
MS
При этом ключ для сортировки находится только в одном из них.
P
а как производится сопоставление изначальное - по индексах?
MS
Да, это ж массив.
P
Да, это ж массив.
Возьми новый массив, в котором изначально сохрани числа от 0 до n-1. Затем отсортируй эти величины(которые по факту индексы), используя значения из массива, по которому хочешь сортировать.
Затем перегрупируй изначальные эллементы в соответствии с полученной последовательностью индексов.
Затем перегрупируй изначальные эллементы в соответствии с полученной последовательностью индексов.
MS
А как перегруппировать так чтоб не разрушить массив индексов?
MS
Ведь если я делаю перегруппировку свопами то мне придётся свопать не только сортируемые элементы но и массив индексов, нет? Или я запутался.
MS
Или дублировать сортируемый массив 🤔
P
values = {'d', 'c', 'b, 'a'}
keys = {4, 3, 2, 1}
Создаёшь новый масив
temp = {0, 1, 2, 3}
Сортируешь temp по компаратору bool cmp(int i1, int i2) return keys[i1] < keys[i2].
После этого получаешь
temp = {3, 2, 1, 0}
keys = {4, 3, 2, 1}
Создаёшь новый масив
temp = {0, 1, 2, 3}
Сортируешь temp по компаратору bool cmp(int i1, int i2) return keys[i1] < keys[i2].
После этого получаешь
temp = {3, 2, 1, 0}
MS
Не, как массив индексов построить я придумал
MS
Я не придумал как им аккуратнее всего воспользоваться.
P
Ок, а типы ключей и значений отличаются?
MS
Технически да.
MS
У меня есть
так что
vector<Keys>
vector<Foos>
vector<Bars>
так что
Keys[i], Foos[i], Bars[i] семантически описывают одну штуку.P
А не проще ли их тогда запихнуть в одну структуру, которую, которую потом можно сортировать в массиве, как единое целое?
MS
Я хочу отсортировать их так, будто это на самом деле
vector<Keys, Foos, Bars>, где ключ для сортировки это Keys.MS
А не проще ли их тогда запихнуть в одну структуру, которую, которую потом можно сортировать в массиве, как единое целое?
Нет, по причинам не относящимся к задаче.
MS
Ну то есть, если бы я мог так сделать, то я бы не приходил в эту конфу с вопросами, не так ли.