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

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

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

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

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

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

Сортировка Шелла. Написал программу, не могу понять, почему сортировка не выполняется - C++
Программа создает динамический массив с рандомным заполнением. Дальше выбор сортировок, пузырьком или сортировка Шелла. Вот она то и не...

Сортировка слиянием. В каком куске кода происходит сортировка и каким именно образом? - C++
Помогите, пожалуйста, разобраться. Подскажите в каком куске кода происходит сортировка и каким именно образом? #include <iostream> ...

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

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

Сортировка Шелла и пирамидальная сортировка для символов - C++
Здраствуйте, можете пожалуйста привести пример сортировок шелла и пиромидальной сортировки для символов, а то ничего не могу ...

Сортировка вектора по полю(Сортировка вставками) - C++
Здравствуйте! Нужно написать сортировку вектора по полю weight класса tomato. Вот класс: #pragma once #include <iostream> ...

4
OhMyGodSoLong
~ Эврика! ~
1244 / 993 / 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
1
castaway
Эксперт С++
4885 / 3020 / 370
Регистрация: 10.11.2010
Сообщений: 11,078
Записей в блоге: 10
Завершенные тесты: 1
27.10.2013, 13:35 #3
Цитата Сообщение от OhMyGodSoLong Посмотреть сообщение
std::sort
Разве она будет работать быстрее чем qsort?
1
OhMyGodSoLong
~ Эврика! ~
1244 / 993 / 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
0
castaway
Эксперт С++
4885 / 3020 / 370
Регистрация: 10.11.2010
Сообщений: 11,078
Записей в блоге: 10
Завершенные тесты: 1
27.10.2013, 14:59 #5
Я написал такой тест.
Из него видно что std::sort работает быстрее.. однако, скомпилировав его через MinGW и запустив на своём ПК оказалось, что qsort почти в два раза быстрее. (флаги оптимизации особой разницы не играют на отношении qsort/std::sort)
С чем это связано я пока не знаю, буду искать причины..
0
27.10.2013, 14:59
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.10.2013, 14:59
Привет! Вот еще темы с ответами:

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

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

2 сортировки: пирамидальная сортировка и сортировка слиянием - C++
Реализовать два улучшенных алгоритма сортировки. Для каждого алгоритма вычислить показатель качества сортировки (количество операций, т.е....

Пирамидальная сортировка и сортировка Шелла - C++
Ребята помогите пожалуйста, я NEWBIE и не могу решить такая задача : Выполнить сортировку по убыванию. Пирамидальная сортировка и...


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

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