Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/6: Рейтинг темы: голосов - 6, средняя оценка - 4.67
51 / 51 / 31
Регистрация: 04.03.2014
Сообщений: 430
1

Десять сортировок. Четыре реализовал, подскажите, какие еще есть?

13.10.2014, 10:57. Просмотров 1209. Ответов 1
Метки нет (Все метки)

Здравствуйте. Получил задание реализовать 10 сортировок. Реализовал методом пузырька, выбора, вставками и быструю QSsort. Подскажите еще методы для сортировок и может ссылки на алгоритмы.
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
13.10.2014, 10:57
Ответы с готовыми решениями:

Какие еще есть конфигурации?
Встретил требование в вакансии Знание платформы 1С 8.2. "Управление Торговлей 11" . Какие еще есть...

Какие еще варианты есть компактнее
Правильно ли я сделал? Есть ли еще варианты, поскидывайте пожалуйста я поразбираюсь Программа...

Какие ещё есть единицы инкапсуляции?
Какие ещё есть единицы инкапсуляции кроме основной единицы - класса? Или класс - основная и...

Какие еще есть графики кроме MSChart и ChartSpace?
Какие еще есть графики кроме MSChart и ChartSpace

1
194 / 93 / 47
Регистрация: 21.02.2011
Сообщений: 3,625
13.10.2014, 11:47 2
Лучший ответ Сообщение было отмечено IrineK как решение

Решение

Алгоритмы устойчивой сортировки

Кликните здесь для просмотра всего текста
Сортировка выбором (англ. Selection sort) — поиск наименьшего или наибольшего элемента и помещение его в начало или конец упорядоченного списка. Сложность алгоритма: O(n2).
Сортировка пузырьком (англ. Bubble sort) — для каждой пары индексов производится обмен, если элементы расположены не по порядку. Сложность алгоритма: O(n2).
Сортировка перемешиванием (англ. Cocktail sort). Сложность алгоритма: O(n2).
Гномья сортировка — схожа с сортировкой пузырьком и сортировкой вставками. Сложность алгоритма — O(n2).
Сортировка вставками (Insertion sort) — Определяем, где текущий элемент должен находиться в упорядоченном списке, и вставляем его туда. Сложность алгоритма: O(n2).
Сортировка слиянием (Merge sort) — выстраиваем первую и вторую половину списка отдельно, а затем объединяем упорядоченные списки. Сложность алгоритма: O(n log n). Требуется O(n) дополнительной памяти.
Сортировка с помощью двоичного дерева (англ. Tree sort). Сложность алгоритма: O(n log n). Требуется O(n) дополнительной памяти.
Сортировка Timsort (англ. Timsort) — комбинированный алгоритм (используется сортировка вставками и сортировка слиянием). Сложность алгоритма: O(n log n). Требуется O(n) дополнительной памяти. Разработан для использования в языке Python.
Сортировка подсчётом (Counting sort). Сложность алгоритма: O(n+k). Требуется O(n+k) дополнительной памяти.
Блочная сортировка (Корзинная сортировка, Bucket sort) — требуется O(k) дополнительной памяти и знание о природе сортируемых данных, выходящее за рамки функций «переставить» и «сравнить». Сложность алгоритма: O(n).


Алгоритмы неустойчивой сортировки

Кликните здесь для просмотра всего текста
Сортировка Шелла (Shell sort). сложность алгоритма: O(n \log^2{n}); попытка улучшить сортировку вставками.
Сортировка расчёской (Comb sort) — сложность алгоритма: O(n \log{n})
Пирамидальная сортировка (сортировка кучи, Heapsort) — сложность алгоритма: O(n \log{n}); превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка
Плавная сортировка (Smoothsort) — сложность алгоритма: O(n \log{n})
Быстрая сортировка (Quicksort), в варианте с минимальными затратами памяти — сложность алгоритма: O(n \log{n}) — среднее время, O(n^2) — худший случай; широко известен как быстрейший из известных для упорядочения больших случайных списков; с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине. При использовании O(n) дополнительной памяти, можно сделать сортировку устойчивой.
Интроспективная сортировка (Introsort) — сложность алгоритма: O(n \log{n}), сочетание быстрой и пирамидальной сортировки. Пирамидальная сортировка применяется в случае, если глубина рекурсии превышает \log{n}.
Терпеливая сортировка (Patience sorting) — сложность алгоритма: O(n \log{n}) — наихудший случай, требует дополнительно O(n) памяти, также находит самую длинную увеличивающуюся подпоследовательность
Stooge sort — рекурсивный алгоритм сортировки с временной сложностью O(n^{\log_{1{,}5}{3}}) \approx O(n^{2.71}).
Поразрядная сортировка (она же цифровая сортировка) — сложность алгоритма: O(nk); требуется O(k) дополнительной памяти.


Непрактичные алгоритмы сортировки

Кликните здесь для просмотра всего текста
Bogosort — O(n·n!) в среднем. Произвольно перемешать массив, проверить порядок.
Сортировка перестановкой — O(n·n!) — худшее время. Для каждой пары осуществляется проверка верного порядка и генерируются всевозможные перестановки исходного массива.
Глупая сортировка (Stupid sort) — O(n3); рекурсивная версия требует дополнительно O(n2) памяти
Bead Sort — O(n) or O(√n), требуется специализированное аппаратное обеспечение
Блинная сортировка (Pancake sorting) — O(n), требуется специализированное аппаратное обеспечение


Алгоритмы, не основанные на сравнениях

Кликните здесь для просмотра всего текста
Блочная сортировка (Корзинная сортировка, Bucket sort)
Лексикографическая или поразрядная сортировка (Radix sort)
Сортировка подсчётом (Counting sort)
2
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
13.10.2014, 11:47

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Какие есть еще паттерны проектирования кроме MVC
Я знаю есть петтерн проектирования MVC а какие еще кроме него есть новые(осовные) петтерны??

Какие еще есть методы быстрой сортировки кроме Хоара?
Какие еще есть методы быстрой сортировки кроме Хоара?

какие накрутки еще можно сделать в этой программе? подскажите, пожалуйста!)
Я выполнила задание по информатике согласно условию задачи, но этого недостаточно для высокой...

Какие еще есть способы создания визуальных приложений кроме WinApi?
Здравствуйте, я так понимаю под Windows оконные приложения создаются на WinAPI. Хотел спросить есть...


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

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

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