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

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

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

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

31.05.2011, 13:26. Просмотров 1383. Ответов 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 как метод класса использовать я не смогу.

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

Быстрая сортировка для массива обьектов пользовательского класса - C++
Насколько я знаю в Си++ есть встроеная ф-ция быстрой сортировки. Как нею воспользоваться для сортировки массива обьектов моего класса? Хочу...

Быстрая сортировка(сортировка Хоара). Отсортировать фрагмент массива - C++
Мне нужно отсортировать фрагмент массива, расположенный между первым и последним отрицательным элементом. Немогу понять как устоновить...

Быстрая сортировка (сортировка Хоара) для связных списков - C++
есть у кого готовый алгоритм? или подскажите как реализовать

Поместить в динамически расширяемый массив объекты класса, производные от базового абстрактного класса - C++
Помогите пожалуйста новичку! (мне). Я хочу создать динамически расширяющийся массив указателей на базовый абстрактный класс,...

C/C++ FAQ :: Быстрая сортировка (сортировка Хоара) - C++
Вопрос, скорее академический, по мотивам реализации. Вот в faq приведена реализация этого метода сортировки на C++. В коде есть следующий...

Быстрая сортировка (сортировка методом Хоара) - C++
Ввести массив x1,x2,...,x20 в диапазоне . Требуется расположить отрицательные элементы в порядке убывания. Вывести массивы до и после...

7
volovzi
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
31.05.2011, 20:02 #2
В твоём методе хорошо бы избавиться от глобальной переменной "junkspace::x". А так, в принципе, он имеет право на существование.
Ещё можно переделать класс так, чтобы хранить не два массива координат по осям, а один массив пар координат.
0
Евгений М.
1035 / 976 / 54
Регистрация: 28.02.2010
Сообщений: 2,829
Завершенные тесты: 2
31.05.2011, 20:21  [ТС] #3
Цитата Сообщение от volovzi Посмотреть сообщение
Ещё можно переделать класс так, чтобы хранить не два массива координат по осям, а один массив пар координат.
А смысл поменяется?
0
volovzi
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
31.05.2011, 20:32 #4
Не понял. Смысл чего?
0
Евгений М.
1035 / 976 / 54
Регистрация: 28.02.2010
Сообщений: 2,829
Завершенные тесты: 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;
        }
};
Я все правильно понял?
0
volovzi
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
01.06.2011, 11:42 #6
Нет, я имею в виду использовать вот такой контейнер:
C++
1
std::vector<std::pair<double, double> >
И сортировать его самого, а не индексы.
0
Евгений М.
1035 / 976 / 54
Регистрация: 28.02.2010
Сообщений: 2,829
Завершенные тесты: 2
01.06.2011, 12:50  [ТС] #7
Цитата Сообщение от volovzi Посмотреть сообщение
И сортировать его самого, а не индексы.
А можно пример? С помощью qsort такое врядли можно сделать.
0
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;
}
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.06.2011, 12:57
Привет! Вот еще темы с ответами:

Классы и объекты в С++, компонента класса и экземпляр класса - C++
Вариант 8. ИЗДЕЛИЕ наименование– char* шифр– char* тип упаковки– char* количество– int 1. Определить пользовательский ...

Сортировка Хоара / Быстрая сортировка - C++
Доброго времени суток. Написал реализацию алгоритма быстрой сортировки. void SortHhoar(int *arr,int f,int l)//Хоара { int mid = (f...

Сортировка расчёской и быстрая сортировка - C++
В файле in.txt записана последовательность целых чисел. Заданными методами отсортировать числа и записать в файлы out1.txt и out2.txt....

Составить описание класса "3D вектор". Объявить объекты класса и продемонстрировать работу методов - C++
Возникли сложности при решении задачи. Буду признателен тем, кто поможет. Задание: Составить описание класса. Объявить объекты класса...


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

Или воспользуйтесь поиском по форуму:
8
Yandex
Объявления
01.06.2011, 12:57
Ответ Создать тему
Опции темы

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