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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.82
Евгений М.
1034 / 975 / 53
Регистрация: 28.02.2010
Сообщений: 2,818
Завершенные тесты: 2
#1

Быстрая сортировка и объекты класса - C++

31.05.2011, 13:26. Просмотров 1361. Ответов 7
Метки нет (Все метки)

На днях столкнулся с такой задачей. Попробую ее сформулировать.
Дан класс.
C++
1
2
3
4
5
6
7
8
class A
{
...
vector<double> x;
vector<double> y;
void output(); // вывод на экран
...
}
x,y - используются как массивы координат точек. т.е. x[i], y[i] - это относится к одной точке.
Нужно вывести, например на экран, координаты точек так, чтобы x-координата выводилась по возрастанию. В качестве алгоритма сортировки использовать только быструю сортировку.

Придумал следующее решение.
Вспомогательное пространство имен:
C++
1
2
3
4
5
6
7
8
9
10
11
12
namespace junkspace
{
    vector<double>* x;
 
    int compare(const void* aa, const void* bb)
    {
        int a = *(int*)aa;
        int b = *(int*)bb;
        if (x->at(a)<x->at(b)) return 1;
        else return -1;
    }
};
Реализация метода вывода:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void A::output()
{
        size_t* na;
    size_t n = x.size();
 
    if (n==0) return;
 
    na = new size_t [n];
 
    for (size_t i=0; i<n; i++)
        na[i] = i;
 
    junkspace::x = &x;
    qsort(na, n, sizeof(size_t), junkspace::compare);
 
    for (size_t i=0; i<n; i++)
    {
        cout <<  x[na[i]] << " " << y[na[i]] << endl;
    }
}
na - массив индексов. Я его сортирую с помощью qsort. B качестве функции сортировки использую compare из junkspace. compare как метод класса использовать я не смогу.

Этот метод мне вполне устраивает.
Вопрос: есть ли другие методы решения этой задачи?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.05.2011, 13:26     Быстрая сортировка и объекты класса
Посмотрите здесь:

Быстрая сортировка C++
C/C++ FAQ :: Быстрая сортировка (сортировка Хоара) C++
C++ Быстрая сортировка
Быстрая сортировка для массива обьектов пользовательского класса C++
Быстрая сортировка (сортировка Хоара) для связных списков C++
Составить описание класса "3D вектор". Объявить объекты класса и продемонстрировать работу методов C++
C++ Быстрая сортировка
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
volovzi
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
31.05.2011, 20:02     Быстрая сортировка и объекты класса #2
В твоём методе хорошо бы избавиться от глобальной переменной "junkspace::x". А так, в принципе, он имеет право на существование.
Ещё можно переделать класс так, чтобы хранить не два массива координат по осям, а один массив пар координат.
Евгений М.
1034 / 975 / 53
Регистрация: 28.02.2010
Сообщений: 2,818
Завершенные тесты: 2
31.05.2011, 20:21  [ТС]     Быстрая сортировка и объекты класса #3
Цитата Сообщение от volovzi Посмотреть сообщение
Ещё можно переделать класс так, чтобы хранить не два массива координат по осям, а один массив пар координат.
А смысл поменяется?
volovzi
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
31.05.2011, 20:32     Быстрая сортировка и объекты класса #4
Не понял. Смысл чего?
Евгений М.
1034 / 975 / 53
Регистрация: 28.02.2010
Сообщений: 2,818
Завершенные тесты: 2
01.06.2011, 06:31  [ТС]     Быстрая сортировка и объекты класса #5
Задам по другому.
Вы предлагаете где-то так:
C++
1
2
3
4
5
6
class A
{
...
vector<POINT> points;
...
}
А сам junkspace:
C++
1
2
3
4
5
6
7
8
9
10
11
12
namespace junkspace
{
        vector<POINT>* points;
 
        int compare(const void* aa, const void* bb)
        {
                int a = *(int*)aa;
                int b = *(int*)bb;
                if (points->at(a).x->points->at(b).x) return 1;
                else return -1;
        }
};
Я все правильно понял?
volovzi
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
01.06.2011, 11:42     Быстрая сортировка и объекты класса #6
Нет, я имею в виду использовать вот такой контейнер:
C++
1
std::vector<std::pair<double, double> >
И сортировать его самого, а не индексы.
Евгений М.
1034 / 975 / 53
Регистрация: 28.02.2010
Сообщений: 2,818
Завершенные тесты: 2
01.06.2011, 12:50  [ТС]     Быстрая сортировка и объекты класса #7
Цитата Сообщение от volovzi Посмотреть сообщение
И сортировать его самого, а не индексы.
А можно пример? С помощью qsort такое врядли можно сделать.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.06.2011, 12:57     Быстрая сортировка и объекты класса
Еще ссылки по теме:

Быстрая сортировка (сортировка методом Хоара) C++
C++ Сортировка Хоара / Быстрая сортировка
C++ Классы и объекты в С++, компонента класса и экземпляр класса
C++ Сортировка расчёской и быстрая сортировка
C++ Поместить в динамически расширяемый массив объекты класса, производные от базового абстрактного класса

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

Или воспользуйтесь поиском по форуму:
volovzi
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
01.06.2011, 12:57     Быстрая сортировка и объекты класса #8
Схематично — как-то так:
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
#include <iostream>
#include <vector>
 
typedef std::vector<std::pair<double, double> > points_container;
 
void random_fill (points_container & points)
{    
    for (int i = 0; i < points.size(); ++i)
    {
        points[i] = std::make_pair(random() % 10, random() % 10);
    }
}
 
void print_points (const points_container & points)
{
    for (int i = 0; i < points.size(); ++i)
    {
        std::cout << points[i].first <<  ' ' << points[i].second << std::endl;
    }
    std::cout << std::endl;
}
                  
int main()
{
    points_container points(5);
    random_fill(points);
    
    print_points(points);
    std::sort(points.begin(), points.end());
    print_points(points);
    
    return 0;
}
Yandex
Объявления
01.06.2011, 12:57     Быстрая сортировка и объекты класса
Ответ Создать тему
Опции темы

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