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

Возникли трудности с функцией быстрой сортировки qsort - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.92
Asdf
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 110
09.05.2012, 21:59     Возникли трудности с функцией быстрой сортировки qsort #1
Добрый вечер. Есть массив прямоугольников со своей высотой и шириной, надо отсортировать отдельно по высоте, ширине и площади прямоугольника. Так вот, основное есть, а вот с сортировкой заминка вышла. Вроде всё как надо написал, но в итоге выводит бред. Подскажите, где я напорол косяков. Может в самой функции сравнения или в описании функции 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
const int n = 10;
 
struct rectangle
{    
    double width, height;
};
int compare(const void * a, const void * b)
{
  if (*(int *)a < *(int *)b) return -1; 
  if (*(int *)a > *(int *)b) return 1; 
  return 0;
}
 
 
int main()
{
    setlocale(0, "Russian");
    int i;
    srand((unsigned)time(NULL));
    rectangle *arr_rectangle = new rectangle[10];
    for (i=0; i<n; i++)
    {
        arr_rectangle[i].height=rand()%10+1;
        arr_rectangle[i].width=rand()%10+1;
        cout << arr_rectangle[i].height << "\t" << arr_rectangle[i].width << endl;
    }
    qsort(arr_rectangle, 10, sizeof(arr_rectangle[i].height), compare);
    cout << "Отсортированный массив по высоте \n" << arr_rectangle[i].height << " " << endl;;
    cout << "Press Any Key to Exit..";
    getch();
    return 0;
    
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.05.2012, 21:59     Возникли трудности с функцией быстрой сортировки qsort
Посмотрите здесь:

задание с функцией qsort(). язык C C++
C++ Функция qsort для сортировки массивов структур
работа с функцией qsort C++
C++ Возникли огромные трудности с задачей. (С++)
C++ Возникли трудности(
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
jambas92
 Аватар для jambas92
58 / 57 / 3
Регистрация: 18.11.2010
Сообщений: 315
09.05.2012, 22:20     Возникли трудности с функцией быстрой сортировки qsort #2
если не ошибаюсь то вот так:

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <iostream>
#include <fstream>
#include <string>
#include <time.h>
using namespace std;
 
const int n = 10;
 
struct rectangle
{    
    double width, height;
};
/*int compare(const void * a, const void * b)
{
  if (*(int *)a < *(int *)b) return -1; 
  if (*(int *)a > *(int *)b) return 1; 
  return 0;
}*/
 
void qsort1(rectangle *a, int n) // width
{
    if (n <= 1)
        return;
    int x = a[n/2].width;
 
    int i = 0;
    int j = n - 1;
    while (1) {
        while (a[i].width < x)
            i++;
        while (a[j].width > x)
            j--;
        if (i <= j) {
            if (i < j) {
                rectangle tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
            }
            i++;
            j--;
        } else {
            break;
        }
    }
    qsort1(a, j + 1);
    qsort1(a + i, n - i);
}
 
void qsort2(rectangle *a, int n) // height
{
    if (n <= 1)
        return;
    int x = a[n/2].height;
 
    int i = 0;
    int j = n - 1;
    while (1) {
        while (a[i].height < x)
            i++;
        while (a[j].height > x)
            j--;
        if (i <= j) {
            if (i < j) {
                rectangle tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
            }
            i++;
            j--;
        } else {
            break;
        }
    }
    qsort2(a, j + 1);
    qsort2(a + i, n - i);
}
 
void qsort3(rectangle *a, int n) // area width * height
{
    if (n <= 1)
        return;
    int x = a[n/2].width * a[n/2].height;
 
    int i = 0;
    int j = n - 1;
    while (1) {
        while (a[i].width * a[i].height < x)
            i++;
        while (a[j].width * a[j].height > x)
            j--;
        if (i <= j) {
            if (i < j) {
                rectangle tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
            }
            i++;
            j--;
        } else {
            break;
        }
    }
    qsort3(a, j + 1);
    qsort3(a + i, n - i);
}
 
int main()
{
    setlocale(0, "Russian");
    int i;
    srand((unsigned)time(NULL));
    rectangle *arr_rectangle = new rectangle[10];
    for (i=0; i<n; i++)
    {
        arr_rectangle[i].height=rand()%10+1;
        arr_rectangle[i].width=rand()%10+1;
        cout << arr_rectangle[i].height << "\t" << arr_rectangle[i].width << endl;
    }
    //qsort(arr_rectangle, 10, sizeof(arr_rectangle[i].height), compare);
    qsort1(arr_rectangle, 10);
    qsort2(arr_rectangle, 10);
    qsort3(arr_rectangle, 10);
    cout << "Отсортированный массив по высоте \n" << arr_rectangle[i].height << " " << endl;;
    cout << "Press Any Key to Exit..";
    return 0;
    
}
Asdf
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 110
09.05.2012, 22:32  [ТС]     Возникли трудности с функцией быстрой сортировки qsort #3
У меня ругаеться на это warning C4244: инициализация: преобразование "double" в "int", возможна потеря данных Это не страшно? А вот сортировку, ту что ты написал, можно как то упростить и используя функцию compare? Может будет выглядеть не так громоздко.
jambas92
 Аватар для jambas92
58 / 57 / 3
Регистрация: 18.11.2010
Сообщений: 315
09.05.2012, 22:38     Возникли трудности с функцией быстрой сортировки qsort #4
Цитата Сообщение от Asdf Посмотреть сообщение
инициализация: преобразование "double" в "int", возможна потеря данных Это не страшно?
потеря данных происходит когда ты преобразуешь скажем 4.3 в int, тогда у тебя будет 4. 0.3 теряешь.
Цитата Сообщение от Asdf Посмотреть сообщение
А вот сортировку, ту что ты написал, можно как то упростить и используя функцию compare?
наверно можно, просто я от руки прописал алгоритм сортировки. Для меня так легче.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
09.05.2012, 22:43     Возникли трудности с функцией быстрой сортировки qsort #5
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int compare(const void * a, const void * b)
{
  rectangle const* pa = reinterpret_cast<rectangle const*>(a);
  rectangle const* pb = reinterpret_cast<rectangle const*>(b);
  if (pa->height < pb->height) return -1; 
  if (pa->height > pb->height) return  1; 
  return 0;
}
 
// ...
 
    qsort(arr_rectangle, 10, sizeof(arr_rectangle[0]), compare);
    cout << "Отсортированный массив по высоте \n";
    for (i=0; i<n; i++)
    {
        cout << arr_rectangle[i].height << "\t" << arr_rectangle[i].width << endl;
    }
 
// ...
Но вообще-то в C++ есть контейнеры и стандартный алгоритм std::sort(), который идеологически более правильный
Asdf
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 110
09.05.2012, 22:52  [ТС]     Возникли трудности с функцией быстрой сортировки qsort #6
А, ну понятно. Ну да, видно что сам писал. Блин... Просто мне по заданию надо использовать стандартную функцию быстрой сортировки. Эт её алгоритм, может сможешь помочь если есть времечко, хотябы с одной из функций, к примеру на ширину. Дальше сам буду пробовать
void qsort( void *base, size_t num, size_t width,
int ( *compare )(const void *elem1, const void *elem2 ) )

Добавлено через 3 минуты
Разъясни пожалуйста вот эту часть
C++
1
2
3
4
rectangle const* pa = reinterpret_cast<rectangle const*>(a);
  rectangle const* pb = reinterpret_cast<rectangle const*>(b);
  if (pa->height < pb->height) return -1; 
  if (pa->height > pb->height) return  1;
И почему там где sizeof(arr_rectangle[0]) ты берёшь 0?

Добавлено через 3 минуты
Ой, все эти стандартные шаблоны и контейнеры я ещё не изучал, поэтому во внимание даже не брал.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
09.05.2012, 22:59     Возникли трудности с функцией быстрой сортировки qsort #7
Цитата Сообщение от Asdf Посмотреть сообщение
Разъясни пожалуйста вот эту часть
Функция сортировки вызывает функцию сравнения и передаёт указатели на 2 элемента. Но эти указатели пустого типа, мы же знаем, что элементами являются прямоугольники. Первые две строчки просто преобразуют тип указателя, а вторые две используют эти указатели чтобы обратиться к нужным полям, в данном случае к высоте.
Можно было в стиле Си написать, примерно так:
C++
1
if (((const rectangle*)a)->height < ((const rectangle*)b)->height) return -1;
Цитата Сообщение от Asdf Посмотреть сообщение
И почему там где sizeof(arr_rectangle[0]) ты берёшь 0?
В этом месте индекс вообще не важен, можно любой подставить, важно что мы хотим узнать размер одного элемента. Можно написать sizeof(rectangle) если тип элементов менять точно не будет, но через элемент массива универсальнее.

Добавлено через 1 минуту
переменные pa и pb просто для удобства, чтобы лишний раз преобразование не записывать.
Asdf
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 110
09.05.2012, 23:07  [ТС]     Возникли трудности с функцией быстрой сортировки qsort #8
Понятно А тогда можно вместо pa и pb брать просто, а и b? Раз мы преобразовали pa и pb в a и b.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
09.05.2012, 23:09     Возникли трудности с функцией быстрой сортировки qsort #9
Ну я в предыдущем ответе пример привёл, когда pa и pb не нужны, да. Но разбираться в этом нагромождении труднее.
Asdf
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 110
09.05.2012, 23:15  [ТС]     Возникли трудности с функцией быстрой сортировки qsort #10
А, ну понятно. Ну да тут ты прав, легче когда всё понятно, а не магия букв )))
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
09.05.2012, 23:25     Возникли трудности с функцией быстрой сортировки qsort #11
Ещё немного подумав замечу, что в данном случае вместо reinterpret_cast, видимо, правильнее использовать static_cast. Хотя ничего не изменится.
Asdf
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 110
13.05.2012, 01:14  [ТС]     Возникли трудности с функцией быстрой сортировки qsort #12
Так, вроде всё окей, но как мне тогда записать если мне надо вычислить площадь прямоугольника? Саму формулу я знаю, как мне в функции compare прописать? ) pa->width*height?
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
13.05.2012, 01:17     Возникли трудности с функцией быстрой сортировки qsort #13
pa->width*pa->height
Asdf
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 110
13.05.2012, 01:22  [ТС]     Возникли трудности с функцией быстрой сортировки qsort #14
Так с этим всё понятно, ток вот я никак не могу понять каким образом можно отсортировать по площади? Если по стороне ещё понятно, то тут возник огромный вопрос...
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
13.05.2012, 01:31     Возникли трудности с функцией быстрой сортировки qsort #15
Ну так же примерно.
C++
1
2
3
4
5
6
7
8
9
10
int compare_by_area(const void * a, const void * b)
{
  rectangle const* pa = static_cast<rectangle const*>(a);
  rectangle const* pb = static_cast<rectangle const*>(b);
  double area_a = pa->width * pa->height;
  double area_b = pb->width * pb->height;
  if (area_a < area_b) return -1; 
  if (area_a > area_b) return  1; 
  return 0;
}
Asdf
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 110
13.05.2012, 01:32  [ТС]     Возникли трудности с функцией быстрой сортировки qsort #16
Не не, мне не сам код, а принцип )))
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
13.05.2012, 01:35     Возникли трудности с функцией быстрой сортировки qsort #17
Ну мне непонятно, что тут может быть непонятного Разные прямоугольники имеют разную площадь. Вот и располагаем их так, чтобы в начале были прямоугольники с маленькой площадью, а в конце с большой. Площадь такая же характеристика, как и размеры сторон.
Asdf
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 110
13.05.2012, 01:36  [ТС]     Возникли трудности с функцией быстрой сортировки qsort #18
Получается, если у меня в массиве 5 элементов и во втором массиве 5, то тогда берётся каждый элемент из массива умножается и выводится как площади и по этим площадям идёт сортировка? )
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
13.05.2012, 01:38     Возникли трудности с функцией быстрой сортировки qsort #19
Ну, как бы да. Тут, кстати, получается, что требуется столько умножений, сколько будет сравнений. Так что в некоторых может оказаться выгодным хранить площадь наряду с размерами, а не вычислять её каждый раз.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.05.2012, 01:47     Возникли трудности с функцией быстрой сортировки qsort
Еще ссылки по теме:

Пожскажите с функцией sort() или qsort() C++
Выполнить сортировку массива с помощью стандартной функции быстрой сортировки qsort C++
Выполнить сортировку массива с помощью стандартной функции быстрой сортировки qsort C++

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

Или воспользуйтесь поиском по форуму:
Asdf
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 110
13.05.2012, 01:47  [ТС]     Возникли трудности с функцией быстрой сортировки qsort #20
Так, получаеться всё окей, тока не совсем красиво. Хочется, чтобы площадь выводилась после сторон, но она сразу подсчитывает 2 точки и выводиться. И очень не красиво получаеться Сделано так, как лучше переделать?
C++
1
2
3
4
5
6
7
8
for (i=0; i<n; i++)
    {
        arr_rectangle[i].width=rand()%10+1;
        arr_rectangle[i].height=rand()%10+1;
        cout << arr_rectangle[i].height << "\t" << arr_rectangle[i].width << endl;
        arr_rectangle[i].area=arr_rectangle[i].width*arr_rectangle[i].height;
        cout << arr_rectangle[i].area << "" << endl;
    }
Yandex
Объявления
13.05.2012, 01:47     Возникли трудности с функцией быстрой сортировки qsort
Ответ Создать тему
Опции темы

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