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

Какие 2 сортировки надо знать, чтобы на все случаи жизни быть застрахованным? - C++

Восстановить пароль Регистрация
 
ferc
2 / 2 / 1
Регистрация: 20.02.2014
Сообщений: 29
20.02.2014, 19:08     Какие 2 сортировки надо знать, чтобы на все случаи жизни быть застрахованным? #1
Всем добрый вечер!
Форум уже давно читаю на правах гостя. Сегодня всерьез решил заняться темой сортировок. Форум очень интересный, уверен, не зря зарегистрировался.

Собственно, сабж:
Прочитал кучу статей о сортировках, о скорости, памяти, но разобраться оказалось трудновато. Раньше я думал, что достаточно знать QuickSort, что можно применять ее всюду и сортить абсолютно любые массивы за наименьшее время. Сегодня узнал, что у qsort есть свои недостатки:
- Даже над отсортированным массивом она производит какие-то действия
- Можно подобрать тесты, когда она работает за O(n*n)
- С рекурсивной реализацией даже при 10 элементах она вызывает сама себя порой 15 раз.

Возможно, в чем-то ошибаюсь, поэтому и спрашиваю. Какие, допустим, две сортировки советуете знать наизусть и применять в различных ситуациях?
Ведь для маленьких массивов лучше одна, для больших - другая.
В принципе, прочитал-то я не мало статей по этому вопросу, хочется послушать советы.

Какие 2 сортировки надо знать, чтобы на все случаи жизни быть застрахованным? ...Или почти на все
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.02.2014, 19:08     Какие 2 сортировки надо знать, чтобы на все случаи жизни быть застрахованным?
Посмотрите здесь:

C++ Выяснить, какие цифры (по одной справа и слева) надо приписать к числу 1022, чтобы полученное число делилось на 7, 8, 9.
как много надо знать? C++
C++ я учусь на высшке на программиста.. какие могут быть задачи на экзамене 1й курс .2й семестр!!.. должны быть классы!!
все случаи использование конструктора копирования C++
Помочь доделать программу (Надо, чтобы все значения вводились с клавиатуры) C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11811 / 6790 / 767
Регистрация: 27.09.2012
Сообщений: 16,840
Записей в блоге: 2
Завершенные тесты: 1
20.02.2014, 19:12     Какие 2 сортировки надо знать, чтобы на все случаи жизни быть застрахованным? #2
Знакомьтесь: Алгоритмы сортировок
ferc
2 / 2 / 1
Регистрация: 20.02.2014
Сообщений: 29
20.02.2014, 19:23  [ТС]     Какие 2 сортировки надо знать, чтобы на все случаи жизни быть застрахованным? #3
Цитата Сообщение от Croessmah Посмотреть сообщение
Спасибо. Хорошая подборка. А если чисто от себя совет? Какими пользуетесь обычно?
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11811 / 6790 / 767
Регистрация: 27.09.2012
Сообщений: 16,840
Записей в блоге: 2
Завершенные тесты: 1
20.02.2014, 19:27     Какие 2 сортировки надо знать, чтобы на все случаи жизни быть застрахованным? #4
Цитата Сообщение от ferc Посмотреть сообщение
Какими пользуетесь обычно?
Выбор сортировки чаще всего зависит от конкретной ситуации
ferc
2 / 2 / 1
Регистрация: 20.02.2014
Сообщений: 29
20.02.2014, 19:31  [ТС]     Какие 2 сортировки надо знать, чтобы на все случаи жизни быть застрахованным? #5
Цитата Сообщение от Croessmah Посмотреть сообщение
Выбор сортировки чаще всего зависит от конкретной ситуации
Вот такая ситуация. Есть 10^9 элементов типа int. Нужно отсортировать их за наименьшее время.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
20.02.2014, 22:13     Какие 2 сортировки надо знать, чтобы на все случаи жизни быть застрахованным? #6
если только 2...
я бы посоветовал MergeSort - гарантированное http://www.cyberforum.ru/cgi-bin/latex.cgi?O(N * \log N) (+ 0 каких-либо подробностей) и сортировку подсчетом.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.02.2014, 22:47     Какие 2 сортировки надо знать, чтобы на все случаи жизни быть застрахованным?
Еще ссылки по теме:

Что надо знать чтобы написать игру на подобии The Binding Of Isaac C++
C++ Какие цифры (по одной справа и слева) надо приписать к числу 1022, чтобы полученное число делилось на 7, 8, 9
Составить программу вычисления корня. Учесть случаи, когда корень не может быть вычислен C++

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

Или воспользуйтесь поиском по форуму:
igorrr37
 Аватар для igorrr37
1593 / 1221 / 118
Регистрация: 21.12.2010
Сообщений: 1,868
Записей в блоге: 7
20.02.2014, 22:47     Какие 2 сортировки надо знать, чтобы на все случаи жизни быть застрахованным? #7
timsort ещё есть
Yandex
Объявления
20.02.2014, 22:47     Какие 2 сортировки надо знать, чтобы на все случаи жизни быть застрахованным?
Ответ Создать тему
Опции темы

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