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

Алгоритмы сортировки массивов - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 145, средняя оценка - 4.80
$$RaMpAgE
 Аватар для $$RaMpAgE
1 / 1 / 0
Регистрация: 04.10.2010
Сообщений: 17
04.10.2010, 23:27     Алгоритмы сортировки массивов #1
Всем привет, хочу для общего развития узнать все способы сортировки массивов.(массив произвольный)
(метод пузырька я знаю)
какой из них самый быстрый?
я только начинаю учить С++ , поэтому прошу что бы программы выглядили попроще для понимания
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.10.2010, 23:27     Алгоритмы сортировки массивов
Посмотрите здесь:

Алгоритмы Сортировки C++
C++ типовые алгоритмы сортировки
C++ алгоритмы сортировки
алгоритмы сортировки массивов C++
Алгоритмы сортировки массивов C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
PointsEqual
ниначмуроФ
 Аватар для PointsEqual
832 / 516 / 33
Регистрация: 12.10.2009
Сообщений: 1,915
04.10.2010, 23:30     Алгоритмы сортировки массивов #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от $$RaMpAgE Посмотреть сообщение
какой из них самый быстрый?
сравнение из википедии:

Сортировка выбором (Selection sort) — Сложность алгоритма: O(n2);
Сортировка Шелла (Shell sort) — Сложность алгоритма: O(n log2 n);
Сортировка расчёской (Comb sort) — Сложность алгоритма: O(n log n)
Пирамидальная сортировка (Сортировка кучи, Heapsort) — Сложность алгоритма: O(n log n); п
Плавная сортировка (Smoothsort) — Сложность алгоритма: O(n log n)
Быстрая сортировка (Quicksort) — Сложность алгоритма: O(n log n) — среднее время, O(n2) — худший случай; широко известен как быстрейший из известных для упорядочения больших случайных списков; с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине
Introsort — Сложность алгоритма: O(n log n), сочетание быстрой и пирамидальной сортировки. Пирамидальная сортировка применяется в случае, если глубина рекурсии превышает log(n).
Patience sorting — Сложность алгоритма: O(n log n + k) — наихудший случай, требует дополнительно O(n + k) памяти, также находит самую длинную увеличивающуюся подпоследовательность
Stooge sort — рекурсивный алгоритм сортировки с временной сложностью .
Поразрядная сортировка — Сложность алгоритма: O(n·k); требуется O(k) дополнительной памяти.
MILAN
 Аватар для MILAN
883 / 777 / 86
Регистрация: 21.02.2009
Сообщений: 1,722
04.10.2010, 23:30     Алгоритмы сортировки массивов #3
Алгоритмы сортировок
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
04.10.2010, 23:38     Алгоритмы сортировки массивов #4
Сообщение было отмечено автором темы, экспертом или модератором как ответ
$$RaMpAgE, разные сортировки оптимальны для разных наборов данных. Есть очень красивый ресурс, который показывает процесс сортировки крайних случаев, все анимированно и очень красиво.
UnderFelixAbove
Сообщений: n/a
17.10.2010, 14:19     Алгоритмы сортировки массивов #5
Знать все сортировки может быть ни к чему. Важно понимать, что сортировки отличаются алгоритмической сложностью и их можно разбить на три класса в зависимости от уровня сложности (O(N*N), O(N*log(N)) и O(N)). Для каждого класса можно выбрать по две-три и досканально их изучить.
Среди квадратичных сортировок можно выделить:
1. Вставками
2. Выбором
Неплохой визуализатор можно поглядеть здесь: ссылка. Сортировку пузырьком не буду приводить в этом списке. Та же сортировка выбором пишется не дольше и для понимания не чуть не сложнее, не говоря уже о том, что работает она в два раза быстрее.

Среди "быстрых" можно посмотреть:
3. Быстрая. (Пожалуй самая популярная)
4. Слиянием. (Не сложная, но требующая дополнительную память + имеет рекурсивную реализацию)
5*. Пирамидальная. (Требует знания и понимания структуры данных КУЧА)

Визуализаторы можно найти здесь: ссылка

Линейные сортировки:
6. Подсчетом
7. Поразрядная.
Но здесь тоже нужно понимать, когда следует их применять. Можно почитать Кнута, если будет тяжеловато, есть много источников в сети.

Вот этих 7 сортировок, на мой взгляд, хватит, чтобы иметь общее представление о сортировках.

Для углубленного изучения можно рассмотреть Плавную сортировку. Она редко встречается. Но мне показалась довольно интересной с точки зрения реализации и понимания.
Описание Плавной сортировки с картинками можно посмотреть здесь
Yandex
Объявления
17.10.2010, 14:19     Алгоритмы сортировки массивов
Ответ Создать тему
Опции темы

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