Всем привет!

Есть два массива:

int a1[100] = { 1, 2, 3, 4, и т.д. }; // отсортирован упорядоченно
int a2[100] = { 3, 5, 1, 54, 32, и т.д.}; // отсортирован согласно некому правилу

массив a2 отсортирован неким образом согласно какому та правилу (т.е. не обязательно упорядоченно). Массив a1 отсортирован упорядоченно. Так вот, как массив а1 отсортировать точно так же как и а2? Пример упрощённый, массивы привёл для простоты, ибо нужен именно алгоритм. В реальности вместо массивов могут быть STL контейнеры со всякими разными структурами, но , т.е. контейнеры совершенно различные, и просто скопировать один в другой не получится.

Здравствуйте, Smooky, Вы писали:

S>Есть два массива:

S>int a1[100] = { 1, 2, 3, 4, и т.д. }; // отсортирован упорядоченно
S>int a2[100] = { 3, 5, 1, 54, 32, и т.д.}; // отсортирован согласно некому правилу

S>массив a2 отсортирован неким образом согласно какому та правилу (т.е. не обязательно упорядоченно). Массив a1 отсортирован упорядоченно. Так вот, как массив а1 отсортировать точно так же как и а2?

Один из вариантов:
1. За O(N) составляем хеш-таблицу H: "ключ из a2" -> "индекс этого ключа в a2"
2. Сортируем a1 стандартным алгоритмом сортировки, используя для сравнения элементов таблицу H. Сложность поиска по хешу — O(1). Т.е. сложность такой сортировки будет тоже стандартной — O(N*LogN).

Здравствуйте, Smooky, Вы писали:

S>Всем привет!

S>Есть два массива:

S>int a1[100] = { 1, 2, 3, 4, и т.д. }; // отсортирован упорядоченно
S>int a2[100] = { 3, 5, 1, 54, 32, и т.д.}; // отсортирован согласно некому правилу

S>массив a2 отсортирован неким образом согласно какому та правилу (т.е. не обязательно упорядоченно). Массив a1 отсортирован упорядоченно. Так вот, как массив а1 отсортировать точно так же как и а2? Пример упрощённый, массивы привёл для простоты, ибо нужен именно алгоритм. В реальности вместо массивов могут быть STL контейнеры со всякими разными структурами, но , т.е. контейнеры совершенно различные, и просто скопировать один в другой не получится.

Если я правильно понял задачу, для нее уже есть решение в boost. Называется permutation iterator.

Здравствуйте, TheBeard, Вы писали:

S>>Есть два массива:

S>>int a1[100] = { 1, 2, 3, 4, и т.д. }; // отсортирован упорядоченно
S>>int a2[100] = { 3, 5, 1, 54, 32, и т.д.}; // отсортирован согласно некому правилу

S>>массив a2 отсортирован неким образом согласно какому та правилу (т.е. не обязательно упорядоченно). Массив a1 отсортирован упорядоченно. Так вот, как массив а1 отсортировать точно так же как и а2? Пример упрощённый, массивы привёл для простоты, ибо нужен именно алгоритм. В реальности вместо массивов могут быть STL контейнеры со всякими разными структурами, но , т.е. контейнеры совершенно различные, и просто скопировать один в другой не получится.

TB>Если я правильно понял задачу, для нее уже есть решение в boost. Называется permutation iterator.

Всё бы хорошо, но, по-видимому, в приведённом примере в массивах — не индексы, а ключи (например, это могут быть вещественные числа).

Здравствуйте, Smooky, Вы писали:

S>Всем привет!

S>Есть два массива:

S>int a1[100] = { 1, 2, 3, 4, и т.д. }; // отсортирован упорядоченно
S>int a2[100] = { 3, 5, 1, 54, 32, и т.д.}; // отсортирован согласно некому правилу

S>массив a2 отсортирован неким образом согласно какому та правилу (т.е. не обязательно упорядоченно). Массив a1 отсортирован упорядоченно. Так вот, как массив а1 отсортировать точно так же как и а2? Пример упрощённый, массивы привёл для простоты, ибо нужен именно алгоритм. В реальности вместо массивов могут быть STL контейнеры со всякими разными структурами, но , т.е. контейнеры совершенно различные, и просто скопировать один в другой не получится.
тут немного попытаюсь потелепатизировать: сначала требуется понять, какое свойство из a2 мы хотим применить к a1. подразумеваю, что у массива неких сущностей a2 есть упорядоченное и стационарное состояние, причем первое описывается с помощью некой перестановки, примененной к стационарному состоянию.
перестановка подразумевается в математическом смысле. ее можно описать, как массив int[] размера 100, где значения пробегают все числа от 1 до 100 по одному разу
далее эту перестановку следует применить к массиву неких сущностей a1:
мета код:

A1Type[100] apply_permutation(A1Type a1[100], int permutation[100])
{
  A1Type result[100];
  for (int i = 0; i < 100; ++i)
  {
    result[i] = a1[permutation[i]];
  }
  return result;
}

Здравствуйте, andy1618, Вы писали:

A>Всё бы хорошо, но, по-видимому, в приведённом примере в массивах — не индексы, а ключи (например, это могут быть вещественные числа).

Вы имеете в виду пример, приведенный топикстартером? Он несколько расплывчато сформулирован, так что я потелепатил немного. Если моя телепатия ошиблась, пусть ТС уточнит требования.

U>

U>A1Type[100] apply_permutation(A1Type a1[100], int permutation[100])
U>{
U>  A1Type result[100];
U>  for (int i = 0; i < 100; ++i)
U>  {
U>    result[i] = a1[permutation[i]];
U>  }
U>  return result;
U>}
U>

Все хорошо, только памяти нужно O(N). А хочется, разумеется, получить in-place permutation. По-моему, тут может помочь разложение перестановки в композицию циклических перестановок (in-place цикл делается элементарно).

Здравствуйте, TheBeard, Вы писали:

TB>Все хорошо, только памяти нужно O(N). А хочется, разумеется, получить in-place permutation.
вообще-то, ТС попросил алгоритм и никаких требований на память не было. я постарался изложил наиболее ясным способом свою мысль.
тут основная проблема понять, что же хочет ТС

Здравствуйте, Smooky, Вы писали:

S>массив a2 отсортирован неким образом согласно какому та правилу (т.е. не обязательно упорядоченно). Массив a1 отсортирован упорядоченно. Так вот, как массив а1 отсортировать точно так же как и а2? Пример упрощённый, массивы привёл для простоты, ибо нужен именно алгоритм. В реальности вместо массивов могут быть STL контейнеры со всякими разными структурами, но , т.е. контейнеры совершенно различные, и просто скопировать один в другой не получится.

Но хотя бы типы данных в обоих контейнерах одинаковые?

Получается следующая картина.
Второй массив частично определяет порядок сравнения над типом (пускай отличный от "естественного" — operator< ).
Частично — потому, что данные, не попавшие в этот массив, совершенно непонятно, как сравнивать.
Понадеемся, что дубликатов в этом массиве нет, иначе бы порядок был противоречивым.

Первый массив определяет множество данных, которые надо упорядочить.
Если среди них есть те, которые не вошли во второй массив, — это беда.

Теперь, собственно, алгоритм.

Для каждого элемента из массива 1 надо проверить, входит ли он в массив 2, и, если входит, расположить его в том же относительном порядке, что и в 2.

ТУПОЕ РЕШЕНИЕ. Линейное по памяти и квадратное по скорости.
Заводим multiset<int> found — множество вхождений элементов a2 в a1, а также set<int> missed — множество ненайденных элементов.
Линейно пробегаем по a1, ищем (увы, линейно) позицию каждого элемента a1[i]==a2[j], если удача — добавляем j в found, если нет — добавляем i в missed.
После этого на основе found — индексы у нас отсортированы — строим выходной массив. И отдельно задумываемся, что же нам делать с missed? (Тут я ничего не посоветую: разве что интерполяцией заниматься).

УМНОЕ РЕШЕНИЕ. Линейнологарифмическое по времени.
Допустим, что
— элементы в a1 упорядочены (собственно, в исходной задаче так и есть; но это ключевой момент по сравнению с тупым решением)
— ненаходимых данных там нет, либо их судьба нам неинтересна
Какая нам разница — бегать по a1 и искать вхождения в a2, или наоборот?
Линейно пробегаем по a2 и проверяем: входит ли очередной элемент a2[j] в a1, и если входит, то сколько раз? (lower_bound и далее считаем длину серии дубликатов). Тут же добавляем это значение в выходной массив.

for(A2::const_iterator j=begin(a2); j!=end(a2); ++j)
  for(A1::const_iterator i=lower_bound(begin(a1),end(a1),*j); i!=end(a1) && *i==*j; ++i)
    a3.push_back(*j);

Если известно, что в a1 нет дубликатов, то внутренний цикл можно упростить, заменив на if.

Здравствуйте, Smooky, Вы писали:

S>Всем привет!

S>Есть два массива:

S>int a1[100] = { 1, 2, 3, 4, и т.д. }; // отсортирован упорядоченно
S>int a2[100] = { 3, 5, 1, 54, 32, и т.д.}; // отсортирован согласно некому правилу

S>массив a2 отсортирован неким образом согласно какому та правилу (т.е. не обязательно упорядоченно). Массив a1 отсортирован упорядоченно. Так вот, как массив а1 отсортировать точно так же как и а2? Пример упрощённый, массивы привёл для простоты, ибо нужен именно алгоритм. В реальности вместо массивов могут быть STL контейнеры со всякими разными структурами, но , т.е. контейнеры совершенно различные, и просто скопировать один в другой не получится.


Вот так например. Вместо double можно подставить другие типы. Главное чтобы их в принципе можно было сортировать.

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

double to_sort[]={1,2,3,4,5};
double sorted[]={23.8,34,90.5,67,901};
int main()
{
    std::map<double,double> m;
    size_t size=sizeof(to_sort)/sizeof(to_sort[0]);
    for(size_t i=0;i<size;++i)
        m[sorted[i]]=to_sort[i];

    std::map<double,double>::iterator it;
    std::vector<double> res;
    for(it=m.begin();it!=m.end();++it)
        res.push_back((*it).second);

}

Здравствуйте, andy1618, Вы писали:

A>Всё бы хорошо, но, по-видимому, в приведённом примере в массивах — не индексы, а ключи (например, это могут быть вещественные числа).

Да, всё верно, в реальном проекте, это ключи разнотипных контейнеров...