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

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

Войти
Регистрация
Восстановить пароль
 
Vladimir_R
0 / 0 / 0
Регистрация: 12.02.2014
Сообщений: 1
#1

Отсортировать одномерный массив по одной из координат - C++

12.02.2014, 17:08. Просмотров 405. Ответов 5
Метки нет (Все метки)

Такая задача.
Есть класс, в котором определена матрица NxM в виде одномерного массива в контейнере vector.
в каждой строки матрицы хранится n-мерные координаты некоторого объекта типа x1,x2,x3,xn,v1,v2,v3,vn
Требуется отсортировать этот одномерный массив по одной из координат, например по координате x2.
Т.е. нужно переставить строки этой матрицы таким образом, чтобы в каждой строке x2 (второй элемент строки) возрастал. Т.е. сверху матрицы были строки с меньшим вторым элементом, а снизу с большим.
Приходится обрабатывать огромные массивы данных, поэтому скорость и экономия памяти в данной задаче критична. По этому как инструмент сортировки были выбраны стандартные std:sort либо stdlib qsort.
Так же хочу обратить внимание на то что данная матрица представлена в виде ОДНОмерного массива и досуп к n-му элементу m-ой строки в матрице NxM осуществляется как не A[m][n], а вот так A[m*N+n]. Это сделано в целях упрощения задачи и экономии памяти.

Итак, требуется реализовать сортировку матрицы с помощью либо std::sort, либо stdlib qsort, с заданным параметром сортировки (по какому значению сортировать). и реализовать её надо полностью как метод класса.

Вот что сейчас получилось:
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
template <typename Tfloat>
class particle_beem
{
    public:
        vector <Tfloat> arr;
 
        particle_beem(int dim, int count_el);
        ~particle_beem();
 
        int resize(int count_el);
        int set_dim(int dim);
        int data_create_rand(Tfloat dXmin, Tfloat dXmax, Tfloat dVmin, Tfloat dVmax);
        int data_write_to_file(const char *cFile_name);
        int data_read_from_file(const char *cFile_name);
        int data_sort_by_coordinate(/*тут необходимо передавать как параметр, по какому элементу сортировать*/);
 
    protected:
 
    private:
        int dimension;
        int count_eliments;
 
        static int sort_func(const void *a, const void *b)
        {
            Tfloat* a1=(Tfloat*) a;
            Tfloat* b1=(Tfloat*) b;
 
            //cout<<"sort:"<<a1[2]<<"   "<<b1[2]<<endl;
            return a1[1] - b1[1];  //1 - это по какому элементу идет сортировка, т.е. по второму
        }
 
};
 
//....всякий код....
 
template <typename Tfloat>
int particle_beem<Tfloat>::data_sort_by_coordinate()
{
    qsort(&arr[0], count_eliments, sizeof(Tfloat)*dimension*2, sort_func);
    return 0;
}
На данный момент этот код работает, но мне необходимо передавать как параметр по какому элементу производить сортировку, и сообщать каким то образом этот параметр компаратору sort_func.

через промежуточное прайват свойство класса не получится, т.к. компаратор является статическим членом класса.
Не статическим членом класса его делать не получается, а выносить из класса его не следует по условиям задачи.
Попробовал реализовать qsort функтором, чтобы передавать параметр сортировки через свойство функтора, но qsort функторы (оно и понятно:-)) совсем не ест.
Подскажите пожалуйста уважаемые форумчани, как мне быть в этой ситуации? как все таки передавать этот параметр сортировки.

И еще. На самом деле, в контексте C++ я с большей радостью, как это и положено использовал бы для сортировки std::sort, и заодно тем самым решил бы проблему с параметром и увеличил производительность. Но я не могу придумать как применить std::sort применительно к данной задачи не распихивая строки матрицы по отдельным контейнерам.
Ведь у меня матрица представлена одномерным массивом.
В qsort я меняю местами блоки памяти заданной длинны, например sizeof(Tfloat)*dimension*2.
а в std::sort мне не указать какими блоками памяти мне оперировать, он сортирует не блоки памяти а элементы массива.
Может подскажите как мне применить std::sort к данной задачи?

Заранее всех благодарю!

Добавлено через 14 часов 13 минут
Поставлю вопрос по другому: как передать в компаратору дополнительный параметр?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.02.2014, 17:08     Отсортировать одномерный массив по одной из координат
Посмотрите здесь:

Отсортировать одномерный массив - C++
Отсортировать одномерный массив длиной N=29 по убыванию методом выбора.

Отсортировать целочисленный одномерный массив - C++
ПОЖАЛУЙСТА ПОМОГИТЕ НАПИСАТЬ ПРОГу: 2) Написать программу, позволяющую сортировать введенный пользовате-лем целочисленный одномерный...

Отсортировать одномерный динамичный массив методом пузырька - C++
Используя команды из данного кода(или просто помогите исправить код) #include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;stdio.h&gt;...

Отсортировать одномерный целочисленный массив сортировкой Шелла - C++
Требуется отсортировать массив сортировкой Шелла. Считывать массив нужно из текстового файла, в котором в одну строку записаны через пробел...

Как отсортировать одномерный динамический массив с помощью указателей? - C++
Как отсортировать одномерный динамический массив с помощью указателей?

Переписать все элементы з матрицы С в одномерный массив F, отсортировать его по возрастанию - C++
В мастрици С количество столбик в каждой строке случайным натуральным числом с интервала (a; b) но общее количество элементов ...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
programina
1914 / 599 / 37
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
12.02.2014, 17:28     Отсортировать одномерный массив по одной из координат #2
Vladimir_R, вместо координат храните в массиве обьекты с координатами. Ваш вопрос отпадет сам собой.
Somebody
2786 / 1600 / 145
Регистрация: 03.12.2007
Сообщений: 4,190
Завершенные тесты: 1
12.02.2014, 17:56     Отсортировать одномерный массив по одной из координат #3
Я так понимаю, объекты не хочется, потому что их много, и в каждом из них будет лишний раз храниться размерность. Но тут тогда вопрос: а точно надо, чтобы этот dimension был динамическим? Тут только из-за этого все проблемы.
programina
1914 / 599 / 37
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
12.02.2014, 18:21     Отсортировать одномерный массив по одной из координат #4
Цитата Сообщение от Somebody Посмотреть сообщение
их много, и в каждом из них будет лишний раз храниться размерность.
Какая размерность?
Somebody
2786 / 1600 / 145
Регистрация: 03.12.2007
Сообщений: 4,190
Завершенные тесты: 1
12.02.2014, 18:42     Отсортировать одномерный массив по одной из координат #5
Цитата Сообщение от programina Посмотреть сообщение
Какая размерность?
Пространства, в котором координаты. Независимо от того, будет ли это std::vector или какой-то свой класс координат, учитывая, что размер на этапе компиляции неизвестен, он всё равно будет хранить адрес массива и размер.

Добавлено через 3 минуты
Самое нормальное, что могу придумать, - это сортировка массива указателей/индексов std::sort'ом. Оно, конечно, память ест, но по времени явно будет лучше, чем гонять все координаты туда-сюда при сортировке.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.02.2014, 18:43     Отсортировать одномерный массив по одной из координат
Еще ссылки по теме:

Считать одномерный массив с файла, отсортировать его использую рекурсивный вызов функции - C++
Нужно написать прогу на Си, самую элементарную... Считать одномерный массив с файла, отсортировать его использую рекурсивный вызов функции,...

Одномерный массив: отсортировать так, чтобы вначале шли положительные элементы, а затем - отрицательные - C++
Помогите пожалуйста с задачей. Надо в одномерном массиве поменять элементы так, чтоб вначале шли положительные, затем нули , затем...

Заполнить случайныйми числами одномерный динамический массив; отсортировать его методом пузырьковой сортировки - C++
В плюсах полный ноль...помогите пожалуйста создать одномерный массив через new и delete его сортировку пузырьком и вывод. Заранее спасибо.

Сформировать из элементов матрицы меньше нуля одномерный массив, отсортировать его по убыванию методом выбора - C++
Дан двумерный массив N X M. Сформировать из элементов меньше нуля одномерный массив отсортировать его по убыванию методом выбора


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

Или воспользуйтесь поиском по форуму:
programina
1914 / 599 / 37
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
12.02.2014, 18:43     Отсортировать одномерный массив по одной из координат #6
Somebody, мне показалось, что вы имеете в виду, что если хранить обьекты внутри вектора, то на это потратится много памяти.
Yandex
Объявления
12.02.2014, 18:43     Отсортировать одномерный массив по одной из координат
Ответ Создать тему
Опции темы

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