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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 28, средняя оценка - 4.79
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1305 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
#1

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

17.06.2011, 08:42. Просмотров 4063. Ответов 25
Метки нет (Все метки)

Есть два массива одинаковой размерности. В одном хоть что, во втором целые числа (индексы элементов первого массива). Нужно выполнить сортировку второго массива по заданным полям первого массива.
Используя STL, разумеется.
Всё, что пока смог придумать, это сохранить в компаранде ссылку на первый массив, но терзают смутные сомнения, что есть более элегантное решение. Тем более, что при сортировке первого массива, второй сортировать не поучится таким способом (думаю забить и использовать два индексных массива).
Есть умные идеи?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.06.2011, 08:42
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сортировка индексов алгоритмом std::sort (C++):

Сортировка массива c++ std :: sort() - C++
Дан двумерный массив символов char M, надо отсортировать его при помощи std :: sort(), построчно, т.е. допустим было 00011 11111 ...

Сортировка списка с использованием std::sort - C++
Что-то не получается отсортировать целочисленные данные расположенные в списке, компилятор (VS10) жутко ругается. В чем может быть дело? ...

Сортировка вектора через std::sort - C++
Доброго времени суток, интересует сабж void Sort(list<int> &past) { sort(past.begin(), past.end()); } на такое выдает ...

Сортировка массива структур по выбранному полю с помощью алгоритма std::sort - C++
Не знаю, как правильно передать функцию сравнения в std::sort. Кроме того в моей структуре есть поля одного типа, мне кажется будет...

Почему стандартная сортировка вектора std::sort намного быстрее сортировки вставками/пузырьком? - C++
Здравствуйте, объясните, пожалуйста, как реализована std::sort. Ясно, что через итераторы, но почему такой сильный выигрыш во времени (1.4...

Отличие std::sort От std::qsort - C++
Пишу доклад по программированию, собственно выбрал тему сортировок. вот сейчас хочу расписать отлчиие + и - двух сортировок. но инфу...

25
Luke
39 / 39 / 1
Регистрация: 21.02.2012
Сообщений: 95
16.03.2012, 00:20 #2
решил?
0
Jupiter
Каратель
Эксперт С++
6556 / 3977 / 227
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
16.03.2012, 00:23 #3
Цитата Сообщение от Luke Посмотреть сообщение
правда ведь умнО?
последний элемент массива не учитвается
0
Luke
39 / 39 / 1
Регистрация: 21.02.2012
Сообщений: 95
16.03.2012, 01:15 #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;
}
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1305 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
16.03.2012, 06:45  [ТС] #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), не более.
Грусть.
0
taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
16.03.2012, 07:33 #6
Цитата Сообщение от Deviaphan Посмотреть сообщение
Есть два массива одинаковой размерности. В одном хоть что, во втором целые числа (индексы элементов первого массива). Нужно выполнить сортировку второго массива по заданным полям первого массива.
Используя STL, разумеется.
Всё, что пока смог придумать, это сохранить в компаранде ссылку на первый массив, но терзают смутные сомнения, что есть более элегантное решение. Тем более, что при сортировке первого массива, второй сортировать не поучится таким способом (думаю забить и использовать два индексных массива). Есть умные идеи?
Задачу нельзя решить параллельно, так как массивы связаны.
0
fasked
Эксперт С++
4942 / 2522 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
16.03.2012, 08:23 #7
Цитата Сообщение от Deviaphan Посмотреть сообщение
Параллельная сортировка массивов
Цитата Сообщение от Deviaphan Посмотреть сообщение
Нужно выполнить сортировку второго массива по заданным полям первого массива.
Цитата Сообщение от Deviaphan Посмотреть сообщение
следует интерпретировать как константу, т.е. менять местами элементы нельзя, сортировать нужно именно index. Элементы в mass занимают до нескольких мегабайт, так что не трогай mass!
Что-то как-то не увязываются между собой условия... Можешь на примере показать? Подкинь данных тестовых: вход, выход.
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1305 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
16.03.2012, 08:35  [ТС] #8
Цитата Сообщение от taras atavin Посмотреть сообщение
Задачу нельзя решить параллельно
Параллельно не в смысле многопоточно, а именно в смысле связности. Т.е. сортируя один массив синхронно сортировать второй.


Цитата Сообщение от fasked Посмотреть сообщение
как-то не увязываются между собой условия
Не правильно назвал тему.)
Привожу пример:
БД и таблицы индексов. Каждую таблицу индексов нужно сортировать в соответствии с заданным столбцом или группой столбцов в матрице. Т.е. нужно сортировать индексы в одном массиве используя значения для сравнения из другого массива.
Задача элементарная, решается элементарно... а вот с использованием std::sort всё не столь тривиально получается.
0
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
16.03.2012, 08:37 #9
Можно пример? На числовых значениях
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1305 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
16.03.2012, 08:41  [ТС] #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
0
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
16.03.2012, 08:45 #11
Почему нельзя скопировать массив,который не нужно трогать и сортировать его как обычно? Добавив пару операций присваивания для второго
0
Luke
39 / 39 / 1
Регистрация: 21.02.2012
Сообщений: 95
16.03.2012, 08:47 #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}

все верно?
0
taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
16.03.2012, 08:48 #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 - массив индексов.
0
Luke
39 / 39 / 1
Регистрация: 21.02.2012
Сообщений: 95
16.03.2012, 08:49 #14
Цитата Сообщение от Deviaphan Посмотреть сообщение
Как ты думаешь, что такое <algorithm>,
я спросил это потому как именно их применение что то заставляет напрягаться в этом случае.
но это наверно от привычки думать открытыми циклами
0
taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
16.03.2012, 08:53 #15
Я привёл лишь пример, в данном случае он проще для понимания, чем вариант, в котором циклы будут спрятаны, да и хороших алгоритмов сортировки. Но пузырёк - худшее возможное решение.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.03.2012, 08:53
Привет! Вот еще темы с ответами:

std::sort + std::lower_bound - C++
тема такая: есть класс person: class Person{ private: string name_; string adress_; long phone_; есть вектор объектов...

std::sort - C++
Достоинства и недостатки делаю таблицу, достоинств и недостатков std::Sort. собственно, не нащёл нечего про это в википедии

std::sort() - C++
Доброго времени суток! Есть некая структура: struct member { int latency; std::vector&lt;int&gt;child; };

algorithm std::sort - C++
Почему так делать нельзя? #include &lt;algorithm&gt; using namespace std; class T { private: int arr;


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

Или воспользуйтесь поиском по форуму:
15
Yandex
Объявления
16.03.2012, 08:53
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru