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

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

Войти
Регистрация
Восстановить пароль
 
ferc
2 / 2 / 1
Регистрация: 20.02.2014
Сообщений: 33
#1

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

20.02.2014, 19:08. Просмотров 389. Ответов 6
Метки нет (Все метки)

Всем добрый вечер!
Форум уже давно читаю на правах гостя. Сегодня всерьез решил заняться темой сортировок. Форум очень интересный, уверен, не зря зарегистрировался.

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

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

Какие 2 сортировки надо знать, чтобы на все случаи жизни быть застрахованным? ...Или почти на все
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.02.2014, 19:08     Какие 2 сортировки надо знать, чтобы на все случаи жизни быть застрахованным?
Посмотрите здесь:
C++ Какие блоки кода надо знать и помнить?
Какие темы нужно знать, чтобы начать работать с DirectX C++
Что надо знать чтобы написать игру на подобии The Binding Of Isaac C++
Составить программу вычисления корня. Учесть случаи, когда корень не может быть вычислен C++
C++ Какие цифры (по одной справа и слева) надо приписать к числу 1022, чтобы полученное число делилось на 7, 8, 9
C++ Выяснить, какие цифры (по одной справа и слева) надо приписать к числу 1022, чтобы полученное число делилось на 7, 8, 9.
C++ я учусь на высшке на программиста.. какие могут быть задачи на экзамене 1й курс .2й семестр!!.. должны быть классы!!
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Croessmah
Модератор
Эксперт CЭксперт С++
12980 / 7292 / 812
Регистрация: 27.09.2012
Сообщений: 18,007
Записей в блоге: 3
Завершенные тесты: 1
20.02.2014, 19:12     Какие 2 сортировки надо знать, чтобы на все случаи жизни быть застрахованным? #2
Знакомьтесь: Алгоритмы сортировок
ferc
2 / 2 / 1
Регистрация: 20.02.2014
Сообщений: 33
20.02.2014, 19:23  [ТС]     Какие 2 сортировки надо знать, чтобы на все случаи жизни быть застрахованным? #3
Цитата Сообщение от Croessmah Посмотреть сообщение
Спасибо. Хорошая подборка. А если чисто от себя совет? Какими пользуетесь обычно?
Croessmah
Модератор
Эксперт CЭксперт С++
12980 / 7292 / 812
Регистрация: 27.09.2012
Сообщений: 18,007
Записей в блоге: 3
Завершенные тесты: 1
20.02.2014, 19:27     Какие 2 сортировки надо знать, чтобы на все случаи жизни быть застрахованным? #4
Цитата Сообщение от ferc Посмотреть сообщение
Какими пользуетесь обычно?
Выбор сортировки чаще всего зависит от конкретной ситуации
ferc
2 / 2 / 1
Регистрация: 20.02.2014
Сообщений: 33
20.02.2014, 19:31  [ТС]     Какие 2 сортировки надо знать, чтобы на все случаи жизни быть застрахованным? #5
Цитата Сообщение от Croessmah Посмотреть сообщение
Выбор сортировки чаще всего зависит от конкретной ситуации
Вот такая ситуация. Есть 10^9 элементов типа int. Нужно отсортировать их за наименьшее время.
salam
160 / 141 / 12
Регистрация: 10.07.2012
Сообщений: 720
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 сортировки надо знать, чтобы на все случаи жизни быть застрахованным?
Еще ссылки по теме:
C++ Надо проверить какие квадраты влезли в круг а какие нет
Все случаи использования конструктора копирования C++
как много надо знать? C++
Помочь доделать программу (Надо, чтобы все значения вводились с клавиатуры) C++
Какие функции нужно знать для участия в олимпиаде C++

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

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

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