MS
И это ведь будет не О(н) по времени.
Size: a a a
2020 November 09
MS
evgeniy
Он же уже есть. Изначатель у вас два массива - значения, индексы, правильно?
А когда у нас есть массив индексов, я ведь могу просто пройти по нему свопая между собой индексы и значения по этим индексам.
e
Сейчас скину свою Python программу, будет понятнее, что я решал. Есть вероятность, что я не так понял задачу :).
MS
вот так
MS
Переслано от Mikola Summer Duck
То есть, что если я буду идти по массиву индексов делая что-то вроде
for i = 0..len(indices)
swap(values[i], values[indices[i]]);
swap(indices[i], indices[indices[i]]);
e
def sort_lst_by_idx_lst(value_lst, index_lst):
cur_val_idx = 0
nxt_val_idx = 0
idx_by_order = 0
while idx_by_order < len(value_lst):
if cur_val_idx == nxt_val_idx:
cur_val_idx, nxt_val_idx = idx_by_order, index_lst[idx_by_order]
cur_val = value_lst[cur_val_idx]
idx_by_order += 1
continue
nxt_val = value_lst[nxt_val_idx]
value_lst[nxt_val_idx] = cur_val
index_lst[cur_val_idx] = cur_val_idx
cur_val_idx, nxt_val_idx = nxt_val_idx, index_lst[nxt_val_idx]
cur_val = nxt_val
### Тестирование
tests = [
(
['_', 'd', 'e', 'h', 'l', 'l', 'l', 'o', 'o', 'r', 'w'],
[5, 10, 1, 0, 2, 3, 9, 4, 7, 8, 6]
),
(
['w', 't', 'o', 'n', 'e', 'o'],
[4, 3, 5, 1, 2, 0]
),
(
['m', 'o', 'u', 's', 'e'],
[0, 1, 2, 3, 4]
),
(
['m', 'o', 'u', 's', 'e'],
[4, 3, 2, 1, 0]
),
(
['e'],
[0]
)
]
for value_lst, index_lst in tests:
sort_lst_by_idx_lst(value_lst, index_lst)
print(value_lst)
e
Результат:
['h', 'e', 'l', 'l', 'o', '_', 'w', 'o', 'r', 'l', 'd']
['o', 'n', 'e', 't', 'w', 'o']
['m', 'o', 'u', 's', 'e']
['e', 's', 'u', 'o', 'm']
['e']
MS
Воу такое лучше на гист куда-то.
MS
Ну и нет, изначальная задача — есть много массивов, нужно применить к ним одинаковую сортировку при том, что ключ для сортировки находится только в одном из них.
e
Я понял так: есть массив со значениями и к нему есть массив с индексами этих значений. Нужно навести порядок в массиве со значениями, используя индексы.
MS
evgeniy
Я понял так: есть массив со значениями и к нему есть массив с индексами этих значений. Нужно навести порядок в массиве со значениями, используя индексы.
смотри выше
e
смотри выше
Да, что это сортировочные ключи, а не индексы я подзабыл, читая последующие комментарии, где речь шла об индексах.
MS
evgeniy
Да, что это сортировочные ключи, а не индексы я подзабыл, читая последующие комментарии, где речь шла об индексах.
Нет, сортированные индексы.
MS
Но они являются подробностью реализации.
e
Примерчик бы какой-нибудь...
e
Как выглядят два изначальных массива.
e
И что нужно получить.
MS
evgeniy
Примерчик бы какой-нибудь...
in:
values: ['b', 'o', 'k', 'a', 't', 'r'];
others: [2, 4, 3, 1, 9, 8];
nthers: [8, 6, 7, 9, 4, 5];
out:
values: ['a', 'b', 'k', 'o', 'r', 't']
others: [1, 2, 3, 4, 8, 9]
nthers: [9, 8, 7, 6, 5, 4]
MS
Массивов произвольное количество.
MS
Ключ сортировки только в
values, к остальным массивам нужно применить пермутацию являющуюся результатом сортировки values.