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

Работа функции qsort - объяснить работу функции - C++

Восстановить пароль Регистрация
 
ыфырф1992
25 / 25 / 12
Регистрация: 08.04.2012
Сообщений: 199
17.07.2014, 20:17     Работа функции qsort - объяснить работу функции #1
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<cstdlib>
int mysort(const void *arg1, const void *arg2);
int main() {
    const short ARR_SIZE=5;
    int arr[ARR_SIZE]={10,5,6,1,3};
    std::qsort(arr, ARR_SIZE, sizeof (int), mysort); 
    for (int i=0;i<ARR_SIZE;++i) {
        std::cout<<arr[i]<<std::endl;
    }
    std::cin.get();
    return 0;
}
int mysort (const void *arg1, const void *arg2) {
    return *(int*)arg1-*(int*)arg2;
}
код взят из учебника, для меня не понятно как работает вот этот эта пользовательская функция
C++
1
2
3
int mysort (const void *arg1, const void *arg2) {
    return *(int*)arg1-*(int*)arg2;
}
прошу подробно объяснить. Не знаю как сформулировать вопрос более точнее, так как мне в этой функции почти все не понятно.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Vourhey
Почетный модератор
6469 / 2244 / 123
Регистрация: 29.07.2006
Сообщений: 12,635
17.07.2014, 20:22     Работа функции qsort - объяснить работу функции #2
Из одного целого вычитается другое целое, результат возвращается.
ыфырф1992
25 / 25 / 12
Регистрация: 08.04.2012
Сообщений: 199
17.07.2014, 20:27  [ТС]     Работа функции qsort - объяснить работу функции #3
Vourhey, не это понятно. Вот например зачем тут
C++
1
(const void *arg1, const void *arg2)
void.
C++
1
2
3
{
    return *(int*)arg1-*(int*)arg2;
}
возвращение значений с помошью return с таким я раньше не сталкивался, как это работает? Вот нафиг здесь *(int*). arg1 это я как понимаю текущее значение элемента массива.
Vourhey
Почетный модератор
6469 / 2244 / 123
Регистрация: 29.07.2006
Сообщений: 12,635
17.07.2014, 20:36     Работа функции qsort - объяснить работу функции #4
Цитата Сообщение от ыфырф1992 Посмотреть сообщение
Вот например зачем тут
Код C++
1
(const void *arg1, const void *arg2)
А ты читал в документации, какой параметр qsort принимает последним? Почитай.
Цитата Сообщение от ыфырф1992 Посмотреть сообщение
возвращение значений с помошью return с таким я раньше не сталкивался
Что значит не сталкивался? Всегда в С++ так и возвращаются значения из функций. (не учитывая передачу указателей и ref в параметрах). Если знаешь другой способ возвращения значения - пиши.
Цитата Сообщение от ыфырф1992 Посмотреть сообщение
Вот нафиг здесь *(int*)
Чтобы привести void* к целому к указателю на целое и потом к целому числу. Читаем про явное приведение типов.
Цитата Сообщение от ыфырф1992 Посмотреть сообщение
arg1 это я как понимаю текущее значение элемента массива.
Да, одно из.
ыфырф1992
25 / 25 / 12
Регистрация: 08.04.2012
Сообщений: 199
17.07.2014, 20:41  [ТС]     Работа функции qsort - объяснить работу функции #5
Vourhey, прощу прощения, я вроде как учусь по книге и все что вы перечислили я еще не увидел в главах этой книги. Буду учить далее и посмотрю и почитаю то что вы посоветовали
Vourhey
Почетный модератор
6469 / 2244 / 123
Регистрация: 29.07.2006
Сообщений: 12,635
17.07.2014, 20:51     Работа функции qsort - объяснить работу функции #6
Цитата Сообщение от ыфырф1992 Посмотреть сообщение
все что вы перечислили я еще не увидел в главах этой книги
Я же не знаю, что это за книга. Значит, найдешь в другом месте, если в книге нет. Хотя, если применяется qsort, в книге стоило бы описать параметры, которые он принимает.
ыфырф1992
25 / 25 / 12
Регистрация: 08.04.2012
Сообщений: 199
20.07.2014, 03:34  [ТС]     Работа функции qsort - объяснить работу функции #7
Vourhey, почитал про приведение типов, прочитал про ключивое слово void. Но не понятна осталось маленькая деталь.
C++
1
2
3
int mysort (const void *arg1, const void *arg2) {
    return *(int*)arg1-*(int*)arg2;
}
Как я понимаю в данном случае ключевое слово void означает что указатель будет "универсальным". Он может ссылаться на любую переменную. Зачем тогда производить явное преобразование типов?Зачем звездочка после int?
Такая запись возможна?
C++
1
2
return *(int)arg1-*(int)arg2// или
return (int)*arg1-(int)*arg2
Vtulhu
369 / 375 / 96
Регистрация: 12.08.2011
Сообщений: 1,610
20.07.2014, 17:58     Работа функции qsort - объяснить работу функции #8
Как же компилятор поймет, как вычитать одно из другого, если он не знает, на что указывает этот указатель? Что там лежит по тому адресу, int или double? Сейчас это указатели "вообще". Поэтому надо сказать компилятору, что arg1 и arg2 - это указатели на int. А значит, надо привести их к типу (int*). Возможно, вот так будет понятнее:

C
1
2
3
4
5
6
7
8
int intcmp(const void* va, const void* vb)
{
    int* pa = (int*)aa;
    int* pb = (int*)bb;
    int a = *pa;
    int b = *pb;
    return ( a < b )? -1 : (a != b);
}
Кстати, возвращать в этой функции разность чисел - большая ошибка. Если a = 2000000000, а b = -2000000000, то на 32-битной платформе произойдет переполнение. a - b = -294967296. Будет такой эффект, как будто a < b.
Krock21rus
73 / 73 / 19
Регистрация: 18.11.2013
Сообщений: 369
Завершенные тесты: 2
21.07.2014, 10:50     Работа функции qsort - объяснить работу функции #9
Итак. Вот моё объяснение:

qsort(массив,кол-во элементов,размер одного элемента в байтах,функция сравнения);
подробнее про функцию сравнения, у вас она mysort,

const void* это означает что принимается значение неизвестно какого типа, после в теле функции нужно задать алгоритм:

C++
1
return *(int *)arg1 - *(int *)arg2;
возвратит, если arg1>arg2 положительное значение, иначе отрицательное, если равны то 0, дальше qsort() сама решит что с ними делать

в функции использовано void так как функция рассчитана на разные типы данных, в данном случае на int, поэтому в скобках указано (int *), но, в принципе можно и использовать mysort(const int* a, const int* b);
если функция предназначается только для целочисленных типов данных
Psilon
Master of Orion
 Аватар для Psilon
5742 / 4690 / 619
Регистрация: 10.07.2011
Сообщений: 14,162
Записей в блоге: 5
Завершенные тесты: 4
21.07.2014, 11:03     Работа функции qsort - объяснить работу функции #10
Vtulhu, имхо достаточно просто так:
C++
1
2
3
int mysort (const void *arg1, const void *arg2) {
    return *(int*)arg1 > *(int*)arg2;
}
ыфырф1992, вам достаточно понимать, что QSort - это функция сортировки сравнением, поэтому вы указываете функцию, которая скажет, какой из двух объектов должен быть расположен "раньше" в массиве. Принимается void, потому что вы можете сортировать любые структуры, хоть MyVeryCooLStruct. Достаточно определить отношение "меньше" (с помощью этой функции, которую некорректно назвали mysort), и можно соритровать все, что угодно.
Vtulhu
369 / 375 / 96
Регистрация: 12.08.2011
Сообщений: 1,610
21.07.2014, 14:20     Работа функции qsort - объяснить работу функции #11
Цитата Сообщение от Psilon Посмотреть сообщение
Vtulhu, имхо достаточно просто так:
Наверное, Вы имели в виду вот так:

C
1
2
3
int mysort (const void *arg1, const void *arg2) {
    return ( *(int*)arg1 > *(int*)arg2 )? 1 : -1;
}
Такой способ допустим, если нет равных элементов. Или нас не трогает тот факт, что они будут совершенно бессмысленно рокироваться. Кстати, я так подробно расписал для того, чтобы ТС уяснил пертурбации указателей.
Psilon
Master of Orion
 Аватар для Psilon
5742 / 4690 / 619
Регистрация: 10.07.2011
Сообщений: 14,162
Записей в блоге: 5
Завершенные тесты: 4
21.07.2014, 14:23     Работа функции qsort - объяснить работу функции #12
Vtulhu, ну да.
Такой способ допустим, если нет равных элементов.
а вот это плевать, все равно быстрая сортировка не является устойчивой.
Vtulhu
369 / 375 / 96
Регистрация: 12.08.2011
Сообщений: 1,610
21.07.2014, 15:01     Работа функции qsort - объяснить работу функции #13
Цитата Сообщение от Psilon Посмотреть сообщение
а вот это плевать, все равно быстрая сортировка не является устойчивой.
Есть вопросы дисциплины и гигиены программирования. Тот факт, что нельзя быть чистым все время, не означает, что не надо мыться. Программируя с такой психологической установкой, Вы запустите "эффект разбитых окон".

http://www.adme.ru/psihologiya/teori...h-okon-620055/

http://avl2.info/index.php?option=co...ammer&Itemid=8

http://avl2.info/index.php?option=co...ammer&Itemid=8

http://avl2.info/index.php?option=co...ammer&Itemid=8

http://www.youtube.com/watch?v=6bv_RRz24_g
Psilon
Master of Orion
 Аватар для Psilon
5742 / 4690 / 619
Регистрация: 10.07.2011
Сообщений: 14,162
Записей в блоге: 5
Завершенные тесты: 4
21.07.2014, 15:10     Работа функции qsort - объяснить работу функции #14
Vtulhu, омг, при чем тут это? Быстрая сортировка - не устойчивая, значит, она все равно будет менять элементы со одинаковыми весами. Вернее, не будет, но вполне может. Завязываться на реализацию, что "вот на этих входных данных она не меняет что-то там местами" - хуже, чем предполагать, что она всегда не устойчива. Для устойчивой сортировки стоит пользоваться соответствующими средствами - от слияния, до классической IntroSort. Вроде как имеется std::stable_sort, насколько я помню...

Так что какая-то слишком бурная реакция на фразу "не стоит завязываться на реализацию". Считаете иначе?..
Krock21rus
73 / 73 / 19
Регистрация: 18.11.2013
Сообщений: 369
Завершенные тесты: 2
21.07.2014, 16:37     Работа функции qsort - объяснить работу функции #15
Цитата Сообщение от Psilon Посмотреть сообщение
Vtulhu, имхо достаточно просто так:
Код C++
1
2
3
int mysort (const void *arg1, const void *arg2) {
return *(int*)arg1 > *(int*)arg2;
}
Неправильно!, ваша функция должна возвращать int, а вы пытаетесь вернуть bool, да ещё и без соблюдения приоритетов!
Vtulhu
369 / 375 / 96
Регистрация: 12.08.2011
Сообщений: 1,610
21.07.2014, 20:12     Работа функции qsort - объяснить работу функции #16
Цитата Сообщение от Krock21rus Посмотреть сообщение
Неправильно!, ваша функция должна возвращать int, а вы пытаетесь вернуть bool, да ещё и без соблюдения приоритетов!
Ты во всех темах будешь чушь пороть? Чушь уже устала визжать от боли. Ты бы почитал книжку какую-нибудь по С, прежде чем высказывать свое авторитетное мнение столь безапелляционно. Да, и по этикету что-нибудь в библиотеке возьми. А книги вот этого автора, если попадутся, хватай и беги - https://www.ozon.ru/person/291527/
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.07.2014, 13:04     Работа функции qsort - объяснить работу функции
Еще ссылки по теме:

Выполнить сортировку массива с помощью стандартной функции быстрой сортировки qsort C++
Функция strncpy_s - объяснить аргументы функции C++
C++ Объясните работу функции

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

Или воспользуйтесь поиском по форуму:
Krock21rus
73 / 73 / 19
Регистрация: 18.11.2013
Сообщений: 369
Завершенные тесты: 2
23.07.2014, 13:04     Работа функции qsort - объяснить работу функции #17
123
Yandex
Объявления
23.07.2014, 13:04     Работа функции qsort - объяснить работу функции
Ответ Создать тему
Опции темы

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