Форум программистов, компьютерный форум CyberForum.ru

Сортировка индексов алгоритмом std::sort - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 28, средняя оценка - 4.79
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
17.06.2011, 08:42     Сортировка индексов алгоритмом std::sort #1
Есть два массива одинаковой размерности. В одном хоть что, во втором целые числа (индексы элементов первого массива). Нужно выполнить сортировку второго массива по заданным полям первого массива.
Используя STL, разумеется.
Всё, что пока смог придумать, это сохранить в компаранде ссылку на первый массив, но терзают смутные сомнения, что есть более элегантное решение. Тем более, что при сортировке первого массива, второй сортировать не поучится таким способом (думаю забить и использовать два индексных массива).
Есть умные идеи?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.06.2011, 08:42     Сортировка индексов алгоритмом std::sort
Посмотрите здесь:

C++ std::sort()
Сортировка массива структур по выбранному полю с помощью алгоритма std::sort C++
C++ algorithm std::sort
std::sort + std::lower_bound C++
Отличие std::sort От std::qsort C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Luke
37 / 37 / 1
Регистрация: 21.02.2012
Сообщений: 95
16.03.2012, 00:20     Сортировка индексов алгоритмом std::sort #2
решил?
Jupiter
Каратель
Эксперт C++
6542 / 3962 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
16.03.2012, 00:23     Сортировка индексов алгоритмом std::sort #3
Цитата Сообщение от Luke Посмотреть сообщение
правда ведь умнО?
последний элемент массива не учитвается
Luke
37 / 37 / 1
Регистрация: 21.02.2012
Сообщений: 95
16.03.2012, 01:15     Сортировка индексов алгоритмом std::sort #4
Jupiter, это чтоб не было последней перестановки. так задумано. немного поправил условия.
непонятно зачем стл приплетать в такие задачки.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <algorithm>
 
 
int main() 
{
 
    int mass [15] = {1,24,56,78,9,2,7,0,34,67,55,333,88,0,12,};
 
    int index [15] = {1,4,2,3,5,6,7,9,8,0,14,12,13,11,10};
    
    
    std::for_each(mass,mass+14,[&index,&mass](int a)->void{   
    
        static int count = 0;
        static int* p = mass;
        if(index[count]!=0)
        std::swap(*p++,mass[index[count++]]);
        else
        {
            ++p;++count;
        }
        
    });
 
 
        return 0;
}
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
16.03.2012, 06:45  [ТС]     Сортировка индексов алгоритмом std::sort #5
Цитата Сообщение от Luke Посмотреть сообщение
непонятно зачем стл приплетать в такие задачки
Как ты думаешь, что такое <algorithm>, std::swap и std::for_each, если не STL?

Цитата Сообщение от Luke Посмотреть сообщение
немного поправил условия.
Исходные условия не верны. Должно быть:
int index [15] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14};
mass[15] следует интерпретировать как константу, т.е. менять местами элементы нельзя, сортировать нужно именно index. Элементы в mass занимают до нескольких мегабайт, так что не трогай mass!
Размер массивов может быть сотни тысяч и миллионы элементов. Допустима сложность N*log(N), не более.
Грусть.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
16.03.2012, 07:33     Сортировка индексов алгоритмом std::sort #6
Цитата Сообщение от Deviaphan Посмотреть сообщение
Есть два массива одинаковой размерности. В одном хоть что, во втором целые числа (индексы элементов первого массива). Нужно выполнить сортировку второго массива по заданным полям первого массива.
Используя STL, разумеется.
Всё, что пока смог придумать, это сохранить в компаранде ссылку на первый массив, но терзают смутные сомнения, что есть более элегантное решение. Тем более, что при сортировке первого массива, второй сортировать не поучится таким способом (думаю забить и использовать два индексных массива). Есть умные идеи?
Задачу нельзя решить параллельно, так как массивы связаны.
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
16.03.2012, 08:23     Сортировка индексов алгоритмом std::sort #7
Цитата Сообщение от Deviaphan Посмотреть сообщение
Параллельная сортировка массивов
Цитата Сообщение от Deviaphan Посмотреть сообщение
Нужно выполнить сортировку второго массива по заданным полям первого массива.
Цитата Сообщение от Deviaphan Посмотреть сообщение
следует интерпретировать как константу, т.е. менять местами элементы нельзя, сортировать нужно именно index. Элементы в mass занимают до нескольких мегабайт, так что не трогай mass!
Что-то как-то не увязываются между собой условия... Можешь на примере показать? Подкинь данных тестовых: вход, выход.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
16.03.2012, 08:35  [ТС]     Сортировка индексов алгоритмом std::sort #8
Цитата Сообщение от taras atavin Посмотреть сообщение
Задачу нельзя решить параллельно
Параллельно не в смысле многопоточно, а именно в смысле связности. Т.е. сортируя один массив синхронно сортировать второй.


Цитата Сообщение от fasked Посмотреть сообщение
как-то не увязываются между собой условия
Не правильно назвал тему.)
Привожу пример:
БД и таблицы индексов. Каждую таблицу индексов нужно сортировать в соответствии с заданным столбцом или группой столбцов в матрице. Т.е. нужно сортировать индексы в одном массиве используя значения для сравнения из другого массива.
Задача элементарная, решается элементарно... а вот с использованием std::sort всё не столь тривиально получается.
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
16.03.2012, 08:37     Сортировка индексов алгоритмом std::sort #9
Можно пример? На числовых значениях
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
16.03.2012, 08:41  [ТС]     Сортировка индексов алгоритмом std::sort #10
Цитата Сообщение от Deviaphan Посмотреть сообщение
Т.е. сортируя один массив синхронно сортировать второй.
Это я опять заврался.
Две разные задачи решать собрался.
Есть вариант, когда именно два массива и сортируя один, нужно сортировать и второй, меняя местами элементы по тем же индексам, что и в первом.
А в другом случае нужно сортировать только второй массив, используя значения для сравнения из первого.

Сперва я первый вариант реализовать хотел, но второй оказался компактнее и более универсальный. К тому же, решение для них обоих одинаковое, так что можешь придумать ответ на любой из двух вопросов.)

Добавлено через 3 минуты
Цитата Сообщение от fasked Посмотреть сообщение
Подкинь данных тестовых: вход, выход.
Вход:
int[5] data 5 1 2 8 4
int[5] index 0 1 2 3 4

Выход
int[5] data 5 1 2 8 4
int[5] index 1 2 4 0 3
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
16.03.2012, 08:45     Сортировка индексов алгоритмом std::sort #11
Почему нельзя скопировать массив,который не нужно трогать и сортировать его как обычно? Добавив пару операций присваивания для второго
Luke
37 / 37 / 1
Регистрация: 21.02.2012
Сообщений: 95
16.03.2012, 08:47     Сортировка индексов алгоритмом std::sort #12
Deviaphan, ты что то сам путаешься со своей же задачей.
если я точно понял то.
index [5] = {0,1,2,3,4};
mass[5] = {11,22,33,44,55};
"сортируем" index как нам надо
{3,0,2,1,4}
mass должен отсортироваться по index
{44,11,33,22,55}

все верно?
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
16.03.2012, 08:48     Сортировка индексов алгоритмом std::sort #13
Цитата Сообщение от Deviaphan Посмотреть сообщение
Вход:
int[5] data 5 1 2 8 4
int[5] index 0 1 2 3 4
Выход
int[5] data 5 1 2 8 4
int[5] index 1 2 4 0 3
А при чём здесь параллелизм и сортировка двух массивов? Это сортировка индексов.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int i;
int l;
int t;
for (i=n-2; i>=0; --i)
{
 for (j=n-1; j>n; --j)
 {
  if (data[index[i]]>data[index[j]])
  {
   t=index[i];
   index[i]=index[j];
   index[j]=t;
  }
 }
}
, где data - основной массив, а index - массив индексов.
Luke
37 / 37 / 1
Регистрация: 21.02.2012
Сообщений: 95
16.03.2012, 08:49     Сортировка индексов алгоритмом std::sort #14
Цитата Сообщение от Deviaphan Посмотреть сообщение
Как ты думаешь, что такое <algorithm>,
я спросил это потому как именно их применение что то заставляет напрягаться в этом случае.
но это наверно от привычки думать открытыми циклами
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
16.03.2012, 08:53     Сортировка индексов алгоритмом std::sort #15
Я привёл лишь пример, в данном случае он проще для понимания, чем вариант, в котором циклы будут спрятаны, да и хороших алгоритмов сортировки. Но пузырёк - худшее возможное решение.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
16.03.2012, 08:53  [ТС]     Сортировка индексов алгоритмом std::sort #16
Цитата Сообщение от AncinetHero Посмотреть сообщение
Почему нельзя скопировать массив
Конкретно, когда возникла эта задача, проблема была в следующем: двусторонний map. люч одновременно является значением и значение является ключём. Два мэпа использовать нельзя, т.к. значения не просто ищутся, но и изменяются. Причём, если с простыми типами это ещё возможно, то вот с объектами всё печальнее. Тип ключа и значения совпадает (он объект), но используются разные поля. Делать копию нельзя, т.к. после обнаружения объект модифицируется. А ещё он большой.
Сделать два мэпа с указателями на объекты тоже нельзя, потому что они хранятся в массиве (список и т.п. отвергнуты на этапе тестирования).
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
16.03.2012, 08:54     Сортировка индексов алгоритмом std::sort #17
Как я понял, нужно сортировать один массив, и одновременно по значениям первого сортировать второй.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
16.03.2012, 09:00  [ТС]     Сортировка индексов алгоритмом std::sort #18
Цитата Сообщение от Luke Посмотреть сообщение
все верно?
Ты правильно понял не правильное название темы.)
index используется для упорядоченного доступа к mass.

Добавлено через 48 секунд
Цитата Сообщение от taras atavin Посмотреть сообщение
Это сортировка индексов.
А теперь сделай то же самое, но с использованием std::sort.

Добавлено через 1 минуту
Цитата Сообщение от Luke Посмотреть сообщение
"сортируем" index как нам надо
Вот это не правильно. Понятие сортировки однозначно. В твоём примере входные и выходные данные будут идентичны (если сортировка по возрастанию используется).

Добавлено через 2 минуты
Цитата Сообщение от Luke Посмотреть сообщение
это наверно от привычки думать открытыми циклами
У меня нет никакого желания писать реализацию бинарной сортировки. Поэтому STL.
Если не можешь использовать стандартные алгоритмы, значит что-то не так с архитектурой.
Luke
37 / 37 / 1
Регистрация: 21.02.2012
Сообщений: 95
16.03.2012, 09:00     Сортировка индексов алгоритмом std::sort #19
C++
1
2
3
4
5
6
7
8
9
10
int index [10] = {3,1,5,7,8,9,0,2,4,6};// не отсортированные индексы.
 
    int mass [10] = {11,22,33,44,55,66,77,88,99,00}; //произвольный массив
 
//int realdata [10] = {44,22,66,88,99,00,11,33,55,77}; данные на выходе берут из mass
// используя индекс.
    //реалдата как бы нет, его держим в уме.
 
 
int value = mass[index[3]]; //это перемещение по реалдата.
при любой перестановке в индексе. на выходе будут соответсвующие новым позициям данный взятые из масс.
при этом масс - константен и не трогается
C++
1
std::sort(index,index+10);//сортируя индекс чем угодно, "сортируем" реалдата не трогая масс
задача сводится не к сортировке а к написанию процедуры взятия значения из масс соответственно индексу.
а для сортировки индекс - пожалуйста, используй тот сорт который душе угоден
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.03.2012, 09:01     Сортировка индексов алгоритмом std::sort
Еще ссылки по теме:

C++ std::sort
Сортировка списка с использованием std::sort C++
Сортировка массива c++ std :: sort() C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
16.03.2012, 09:01  [ТС]     Сортировка индексов алгоритмом std::sort #20
Цитата Сообщение от AncinetHero Посмотреть сообщение
нужно сортировать один массив, и одновременно по значениям первого сортировать второй.
Да. Эта одна из двух задач. Одно из ограничений - использование std::sort.
Yandex
Объявления
16.03.2012, 09:01     Сортировка индексов алгоритмом std::sort
Ответ Создать тему
Опции темы

Текущее время: 16:30. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru