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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 5.00
KostyaKulakov
Заблокирован
#1

Отличие std::sort От std::qsort - C++

12.03.2013, 18:28. Просмотров 2939. Ответов 19
Метки нет (Все метки)

Пишу доклад по программированию, собственно выбрал тему сортировок.

вот сейчас хочу расписать отлчиие + и - двух сортировок. но инфу не могу найти.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.03.2013, 18:28     Отличие std::sort От std::qsort
Посмотрите здесь:

std::sort + std::lower_bound - C++
тема такая: есть класс person: class Person{ private: string name_; string adress_; long phone_; есть вектор объектов...

std::sort() - C++
Доброго времени суток! Есть некая структура: struct member { int latency; std::vector<int>child; };

std::sort - C++
Достоинства и недостатки делаю таблицу, достоинств и недостатков std::Sort. собственно, не нащёл нечего про это в википедии

algorithm std::sort - C++
Почему так делать нельзя? #include <algorithm> using namespace std; class T { private: int arr;

Абстрактный класс и std::sort - C++
Добрый день, Не компилируется строка: std::vector<mtl::io::QtFile*> *vec; ... mtl::misc::Sort(vec); // ЭТА СТРОКА ...

Сортировка массива c++ std :: sort() - C++
Дан двумерный массив символов char M, надо отсортировать его при помощи std :: sort(), построчно, т.е. допустим было 00011 11111 ...

Сортировка индексов алгоритмом std::sort - C++
Есть два массива одинаковой размерности. В одном хоть что, во втором целые числа (индексы элементов первого массива). Нужно выполнить...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
hofmn
Helter Skelter
61 / 61 / 1
Регистрация: 19.09.2012
Сообщений: 133
12.03.2013, 18:38     Отличие std::sort От std::qsort #2
qsort не входит в пространство имен std, это устаревший вариант, который используется только в C.
ITcrusader
Эксперт C++
176 / 162 / 8
Регистрация: 12.02.2013
Сообщений: 410
12.03.2013, 18:39     Отличие std::sort От std::qsort #3
qsort vs sort
google: qsort vs sort c++
Croessmah
Модератор
Эксперт CЭксперт С++
13051 / 7314 / 814
Регистрация: 27.09.2012
Сообщений: 18,050
Записей в блоге: 3
Завершенные тесты: 1
12.03.2013, 18:41     Отличие std::sort От std::qsort #4
Цитата Сообщение от KostyaKulakov Посмотреть сообщение
вот сейчас хочу расписать отлчиие + и - двух сортировок.
Вам отличие алгоритмов, или этих функций?
ITcrusader
Эксперт C++
176 / 162 / 8
Регистрация: 12.02.2013
Сообщений: 410
12.03.2013, 18:41     Отличие std::sort От std::qsort #5
Цитата Сообщение от hofmn Посмотреть сообщение
qsort не входит в пространство имен std, это устаревший вариант, который используется только в C.
в C, которое - подмножество C++
Croessmah
Модератор
Эксперт CЭксперт С++
13051 / 7314 / 814
Регистрация: 27.09.2012
Сообщений: 18,050
Записей в блоге: 3
Завершенные тесты: 1
12.03.2013, 18:42     Отличие std::sort От std::qsort #6
Цитата Сообщение от KostyaKulakov Посмотреть сообщение
собственно выбрал тему сортировок.
Алгоритмы сортировок
KostyaKulakov
Заблокирован
12.03.2013, 19:05  [ТС]     Отличие std::sort От std::qsort #7
а можете рассписать

все "за" и "против", каждой сортировки в нашем случаее qsort И sort

Добавлено через 19 минут
вот тут прочитал

http://ru.wikipedia.org/wiki/Быстрая...82.D0.BA.D0.B8

Неустойчив — если требуется устойчивость, приходится расширять ключ.

какой ключ имеют ввиду?
hofmn
Helter Skelter
61 / 61 / 1
Регистрация: 19.09.2012
Сообщений: 133
12.03.2013, 19:12     Отличие std::sort От std::qsort #8
Цитата Сообщение от KostyaKulakov Посмотреть сообщение
какой ключ имеют ввиду?
Ключ - то, за чем сортируют.
С вики:
"При сортировке записей вида (фамилия, имя, отчество) по фамилии значения ключей для Иванов Сергей и Иванов Иван будут одинаковы, поэтому устойчивая сортировка не переставит Сергея и Ивана местами."
Неустойчивая, соответственно, переставит.
ITcrusader
Эксперт C++
176 / 162 / 8
Регистрация: 12.02.2013
Сообщений: 410
12.03.2013, 23:23     Отличие std::sort От std::qsort #9
Костя, лады. Мне тут стало интересно следующее. Существует множество сортировок (разные по скорости/простоте реализации/стабильности(stable sort)) - раз. Разные алгоритмы сортировок эффективно/неэффективно реализуются на разных структурах данных.

Почему в вопросе привязка к каким-то библиотечным функциям, когда такой огромный простор, где можно разгуляться. А коль уж такая пьянка пошла - получите-распишитесь:

Д. Э. Кнут: Искусство Программирования. Том 3 Сортировка и Поиск

Вот что не горит - так это Кнут. Он будто для тебя её писал
xtorne21st
интересующийся
303 / 274 / 19
Регистрация: 25.09.2010
Сообщений: 1,056
13.03.2013, 01:06     Отличие std::sort От std::qsort #10
qsort и std::sort реализованы по одному и томуже алгоритму quicksort
gray_fox
What a waste!
1443 / 1172 / 61
Регистрация: 21.04.2012
Сообщений: 2,449
Завершенные тесты: 3
13.03.2013, 01:36     Отличие std::sort От std::qsort #11
Вообще вроде не факт, что std::sort использует быструю сортировку, там может быть любой O(n log(n)) алгоритм.
Croessmah
Модератор
Эксперт CЭксперт С++
13051 / 7314 / 814
Регистрация: 27.09.2012
Сообщений: 18,050
Записей в блоге: 3
Завершенные тесты: 1
13.03.2013, 02:24     Отличие std::sort От std::qsort #12
Как можно у алгоритма расписать "за" и "против"? Каждый алгоритм хорош в одном случае и может быть наихудшим решением в другом.
xtorne21st
интересующийся
303 / 274 / 19
Регистрация: 25.09.2010
Сообщений: 1,056
13.03.2013, 14:42     Отличие std::sort От std::qsort #13
Цитата Сообщение от gray_fox Посмотреть сообщение
Вообще вроде не факт, что std::sort использует быструю сортировку, там может быть любой O(n log(n)) алгоритм.
Аргументы в студию
Croessmah
Модератор
Эксперт CЭксперт С++
13051 / 7314 / 814
Регистрация: 27.09.2012
Сообщений: 18,050
Записей в блоге: 3
Завершенные тесты: 1
13.03.2013, 15:56     Отличие std::sort От std::qsort #14
Цитата Сообщение от xtorne21st Посмотреть сообщение
Аргументы в студию
Стандарт:
25.4.1.1 sort [sort]
C++
1
2
3
4
5
template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
1 Effects: Sorts the elements in the range [first,last).
2 Requires: RandomAccessIterator shall satisfy the requirements of ValueSwappable (17.6.3.2). The
type of *first shall satisfy the requirements of MoveConstructible (Table 20) and of MoveAssignable
(Table 22).
3 Complexity: O(N log(N)) (where N == last - first) comparisons.
xtorne21st
интересующийся
303 / 274 / 19
Регистрация: 25.09.2010
Сообщений: 1,056
13.03.2013, 16:03     Отличие std::sort От std::qsort #15
Да, но тут ничего не говорится о разновидностях сортировок. "Эффективность" quicksort O(N log(N)) это факт...
Croessmah
Модератор
Эксперт CЭксперт С++
13051 / 7314 / 814
Регистрация: 27.09.2012
Сообщений: 18,050
Записей в блоге: 3
Завершенные тесты: 1
13.03.2013, 16:04     Отличие std::sort От std::qsort #16
Цитата Сообщение от xtorne21st Посмотреть сообщение
Да, но тут ничего не говорится о разновидностях сортировок.
Вот именно. Вам и написали, что может быть любая с указанной сложностью.
xtorne21st
интересующийся
303 / 274 / 19
Регистрация: 25.09.2010
Сообщений: 1,056
13.03.2013, 16:09     Отличие std::sort От std::qsort #17
Что-то слово "любая" я не наблюдаю. Просто говорится о сложности...
Croessmah
Модератор
Эксперт CЭксперт С++
13051 / 7314 / 814
Регистрация: 27.09.2012
Сообщений: 18,050
Записей в блоге: 3
Завершенные тесты: 1
13.03.2013, 16:12     Отличие std::sort От std::qsort #18
Цитата Сообщение от xtorne21st Посмотреть сообщение
Что-то слово "любая" я не наблюдаю.
Вам уже писали
Цитата Сообщение от gray_fox Посмотреть сообщение
там может быть любой O(n log(n)) алгоритм.
Стандарт регламентирует требования, поведение, но не реализацию.
xtorne21st
интересующийся
303 / 274 / 19
Регистрация: 25.09.2010
Сообщений: 1,056
14.03.2013, 21:00     Отличие std::sort От std::qsort #19
Цитата Сообщение от Croessmah Посмотреть сообщение
O(N log(N))
А что означает буква O? Может кто-то в курсе?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.03.2013, 21:18     Отличие std::sort От std::qsort
Еще ссылки по теме:

Не работает std::sort со списком указателей - C++
Добрый день, товарищи! Делаю лабу по STL в VS 2015. имеется базовый класс и три от него унаследованных. делаю list указателей на базовый...

Std::sort - 3 аргумент другая функция - C++
Здравствуйте. Так все работает //вызывается из наследника sort(group.begin(), group.end(), ( MyClass&amp; obj1, MyClass&amp; obj2)...

Сортировка вектора через std::sort - C++
Доброго времени суток, интересует сабж void Sort(list&lt;int&gt; &amp;past) { sort(past.begin(), past.end()); } на такое выдает ...

Сортировка списка с использованием std::sort - C++
Что-то не получается отсортировать целочисленные данные расположенные в списке, компилятор (VS10) жутко ругается. В чем может быть дело? ...

Отличие CString от std::string - C++
Меня интересует такой глупый вопрос В чём отличия CString от просто string? :-[


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

Или воспользуйтесь поиском по форуму:
hofmn
Helter Skelter
61 / 61 / 1
Регистрация: 19.09.2012
Сообщений: 133
14.03.2013, 21:18     Отличие std::sort От std::qsort #20
Цитата Сообщение от xtorne21st Посмотреть сообщение
А что означает буква O? Может кто-то в курсе?
Хабр
Yandex
Объявления
14.03.2013, 21:18     Отличие std::sort От std::qsort
Ответ Создать тему
Опции темы

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