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

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

Восстановить пароль Регистрация
 
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
27.10.2013, 12:57     Бистрая сортировка #1
Как правильно использовать функцию 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++ FAQ :: Быстрая сортировка (сортировка Хоара) C++
Быстрая сортировка(сортировка Хоара). Отсортировать фрагмент массива C++
2 сортировки: пирамидальная сортировка и сортировка слиянием C++
Быстрая сортировка (сортировка Хоара) для связных списков C++
C++ Сортировка слиянием. В каком куске кода происходит сортировка и каким именно образом?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 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
Эксперт С++
4837 / 2976 / 367
Регистрация: 10.11.2010
Сообщений: 11,008
Записей в блоге: 10
Завершенные тесты: 1
27.10.2013, 13:35     Бистрая сортировка #3
Цитата Сообщение от OhMyGodSoLong Посмотреть сообщение
std::sort
Разве она будет работать быстрее чем qsort?
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 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
Эксперт С++
4837 / 2976 / 367
Регистрация: 10.11.2010
Сообщений: 11,008
Записей в блоге: 10
Завершенные тесты: 1
27.10.2013, 14:59     Бистрая сортировка #5
Я написал такой тест.
Из него видно что std::sort работает быстрее.. однако, скомпилировав его через MinGW и запустив на своём ПК оказалось, что qsort почти в два раза быстрее. (флаги оптимизации особой разницы не играют на отношении qsort/std::sort)
С чем это связано я пока не знаю, буду искать причины..
Yandex
Объявления
27.10.2013, 14:59     Бистрая сортировка
Ответ Создать тему
Опции темы

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