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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 5.00
KostyaKulakov
Заблокирован
12.03.2013, 18:28     Отличие std::sort От std::qsort #1
Пишу доклад по программированию, собственно выбрал тему сортировок.

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

C++ std::sort()
Сортировка индексов алгоритмом std::sort C++
C++ algorithm std::sort
std::sort + std::lower_bound C++
C++ std::sort
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
hofmn
Helter Skelter
 Аватар для hofmn
61 / 61 / 1
Регистрация: 19.09.2012
Сообщений: 133
12.03.2013, 18:38     Отличие std::sort От std::qsort #2
qsort не входит в пространство имен std, это устаревший вариант, который используется только в C.
ITcrusader
Эксперт C++
 Аватар для ITcrusader
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
Модератор
Эксперт С++
 Аватар для Croessmah
11845 / 6824 / 771
Регистрация: 27.09.2012
Сообщений: 16,919
Записей в блоге: 2
Завершенные тесты: 1
12.03.2013, 18:41     Отличие std::sort От std::qsort #4
Цитата Сообщение от KostyaKulakov Посмотреть сообщение
вот сейчас хочу расписать отлчиие + и - двух сортировок.
Вам отличие алгоритмов, или этих функций?
ITcrusader
Эксперт C++
 Аватар для ITcrusader
176 / 162 / 8
Регистрация: 12.02.2013
Сообщений: 410
12.03.2013, 18:41     Отличие std::sort От std::qsort #5
Цитата Сообщение от hofmn Посмотреть сообщение
qsort не входит в пространство имен std, это устаревший вариант, который используется только в C.
в C, которое - подмножество C++
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11845 / 6824 / 771
Регистрация: 27.09.2012
Сообщений: 16,919
Записей в блоге: 2
Завершенные тесты: 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
 Аватар для hofmn
61 / 61 / 1
Регистрация: 19.09.2012
Сообщений: 133
12.03.2013, 19:12     Отличие std::sort От std::qsort #8
Цитата Сообщение от KostyaKulakov Посмотреть сообщение
какой ключ имеют ввиду?
Ключ - то, за чем сортируют.
С вики:
"При сортировке записей вида (фамилия, имя, отчество) по фамилии значения ключей для Иванов Сергей и Иванов Иван будут одинаковы, поэтому устойчивая сортировка не переставит Сергея и Ивана местами."
Неустойчивая, соответственно, переставит.
ITcrusader
Эксперт C++
 Аватар для ITcrusader
176 / 162 / 8
Регистрация: 12.02.2013
Сообщений: 410
12.03.2013, 23:23     Отличие std::sort От std::qsort #9
Костя, лады. Мне тут стало интересно следующее. Существует множество сортировок (разные по скорости/простоте реализации/стабильности(stable sort)) - раз. Разные алгоритмы сортировок эффективно/неэффективно реализуются на разных структурах данных.

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

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

Вот что не горит - так это Кнут. Он будто для тебя её писал
xtorne21st
интересующийся
300 / 271 / 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!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 3
13.03.2013, 01:36     Отличие std::sort От std::qsort #11
Вообще вроде не факт, что std::sort использует быструю сортировку, там может быть любой O(n log(n)) алгоритм.
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11845 / 6824 / 771
Регистрация: 27.09.2012
Сообщений: 16,919
Записей в блоге: 2
Завершенные тесты: 1
13.03.2013, 02:24     Отличие std::sort От std::qsort #12
Как можно у алгоритма расписать "за" и "против"? Каждый алгоритм хорош в одном случае и может быть наихудшим решением в другом.
xtorne21st
интересующийся
300 / 271 / 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
Модератор
Эксперт С++
 Аватар для Croessmah
11845 / 6824 / 771
Регистрация: 27.09.2012
Сообщений: 16,919
Записей в блоге: 2
Завершенные тесты: 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
интересующийся
300 / 271 / 19
Регистрация: 25.09.2010
Сообщений: 1,056
13.03.2013, 16:03     Отличие std::sort От std::qsort #15
Да, но тут ничего не говорится о разновидностях сортировок. "Эффективность" quicksort O(N log(N)) это факт...
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11845 / 6824 / 771
Регистрация: 27.09.2012
Сообщений: 16,919
Записей в блоге: 2
Завершенные тесты: 1
13.03.2013, 16:04     Отличие std::sort От std::qsort #16
Цитата Сообщение от xtorne21st Посмотреть сообщение
Да, но тут ничего не говорится о разновидностях сортировок.
Вот именно. Вам и написали, что может быть любая с указанной сложностью.
xtorne21st
интересующийся
300 / 271 / 19
Регистрация: 25.09.2010
Сообщений: 1,056
13.03.2013, 16:09     Отличие std::sort От std::qsort #17
Что-то слово "любая" я не наблюдаю. Просто говорится о сложности...
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11845 / 6824 / 771
Регистрация: 27.09.2012
Сообщений: 16,919
Записей в блоге: 2
Завершенные тесты: 1
13.03.2013, 16:12     Отличие std::sort От std::qsort #18
Цитата Сообщение от xtorne21st Посмотреть сообщение
Что-то слово "любая" я не наблюдаю.
Вам уже писали
Цитата Сообщение от gray_fox Посмотреть сообщение
там может быть любой O(n log(n)) алгоритм.
Стандарт регламентирует требования, поведение, но не реализацию.
xtorne21st
интересующийся
300 / 271 / 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++
Сортировка списка с использованием std::sort C++
Сортировка массива c++ std :: sort() C++

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

Или воспользуйтесь поиском по форуму:
hofmn
Helter Skelter
 Аватар для hofmn
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
Ответ Создать тему
Опции темы

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