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

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

Войти
Регистрация
Восстановить пароль
 
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
#1

Бистрая сортировка - C++

27.10.2013, 12:57. Просмотров 187. Ответов 4
Метки нет (Все метки)

Как правильно использовать функцию Qsort (как ее использовать для таких типов данных как char, long long int, short?), как ее можно использовать без этой функции (или подскажите более скоростную функцию, которая может заменить эту):
C++
1
2
3
int compare (const void* a, const void* b){
    return *(int *)a - *(int *)b;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.10.2013, 12:57     Бистрая сортировка
Посмотрите здесь:

C++ Сортировка!
C++ сортировка
C++ Сортировка.
Сортировка C++
C++ Сортировка)
Сортировка C++
C++ Сортировка
Сортировка C++
C++ сортировка
C++ Сортировка
Сортировка C++
Сортировка C++ C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1240 / 989 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
27.10.2013, 13:17     Бистрая сортировка #2
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
Как правильно использовать функцию Qsort
C++
1
2
3
4
5
6
7
8
9
10
11
12
// Для числовых типов можно наваять макросы
 
int compare_int(const void *a, const void *b)
{
    return *(const int*)a - *(const int*)b;
}
 
int main()
{
    int array[] = {3, 4, 2, 1, 5};
    qsort(array, sizeof(array) / sizeof(array[0]), sizeof(array[0]), compare_int);
}
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
как ее можно использовать без этой функции
Никак.

Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
или подскажите более скоростную функцию
std::sort
castaway
Эксперт С++
4869 / 3008 / 370
Регистрация: 10.11.2010
Сообщений: 11,059
Записей в блоге: 10
Завершенные тесты: 1
27.10.2013, 13:35     Бистрая сортировка #3
Цитата Сообщение от OhMyGodSoLong Посмотреть сообщение
std::sort
Разве она будет работать быстрее чем qsort?
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1240 / 989 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
27.10.2013, 14:52     Бистрая сортировка #4
Цитата Сообщение от castaway Посмотреть сообщение
Разве она будет работать быстрее чем qsort?
Наверняка. Инлайнинг творит чудеса.

Behold:
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
#include <cstdlib>
 
#include <algorithm>
#include <random>
#include <vector>
 
const int size = 10000000;
 
int compare(const void *a, const void *b)
{
    return (*(static_cast<const int*>(a)) - *(static_cast<const int*>(b)));
}
 
int main()
{
    std::default_random_engine getRandomNumber;
 
    std::vector<int> array(size);
 
    for (int i = 0; i < size; i++) {
        array[i] = getRandomNumber();
    }
 
#ifdef QSORT
    ::qsort(&array.at(0), size, sizeof(int), compare);
#else
    std::sort(array.begin(), array.end());
#endif
}
Код
$ g++ -std=c++11 -O2 -DQSORT cpp.cpp

$ time ./a.out
real    0m3.260s
user    0m0.000s
sys     0m0.031s

$ g++ -std=c++11 -O2 cpp.cpp

$ time ./a.out
real    0m1.674s
user    0m0.000s
sys     0m0.031s
castaway
Эксперт С++
4869 / 3008 / 370
Регистрация: 10.11.2010
Сообщений: 11,059
Записей в блоге: 10
Завершенные тесты: 1
27.10.2013, 14:59     Бистрая сортировка #5
Я написал такой тест.
Из него видно что std::sort работает быстрее.. однако, скомпилировав его через MinGW и запустив на своём ПК оказалось, что qsort почти в два раза быстрее. (флаги оптимизации особой разницы не играют на отношении qsort/std::sort)
С чем это связано я пока не знаю, буду искать причины..
Yandex
Объявления
27.10.2013, 14:59     Бистрая сортировка
Ответ Создать тему
Опции темы

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