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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 145, средняя оценка - 4.80
$$RaMpAgE
1 / 1 / 0
Регистрация: 04.10.2010
Сообщений: 17
#1

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

04.10.2010, 23:27. Просмотров 17898. Ответов 4
Метки нет (Все метки)

Всем привет, хочу для общего развития узнать все способы сортировки массивов.(массив произвольный)
(метод пузырька я знаю)
какой из них самый быстрый?
я только начинаю учить С++ , поэтому прошу что бы программы выглядили попроще для понимания
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.10.2010, 23:27
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритмы сортировки массивов (C++):

алгоритмы сортировки массивов - C++
помогите пожалуйста решить задачу на с++... Если у массива А(50) есть элемент, равный квадрату последнего элемента, то все элементы,...

Алгоритмы сортировки массивов - C++
Дан массив А(50). Отсортировать элементы, предшествующие первому нулевому элементу, по возрастанию алгоритмом «Сортировка вставками».

Алгоритмы поиска и сортировки одномерных массивов - C++
Элементы, которые присутствуют в нескольких экземплярах или в массиве А, или в массиве В (или в обоих массивах) Алгоритмы поиска: •...

Алгоритмы сортировки и обработки двумерных массивов - C++
Пожалуйста помогите! я не понимаю C++ вообще. Очень нужна помощь! Задана матрица размером N×M, N,M<50. Определить k – количество...

Реализовать все алгоритмы сортировки, оформив решение в виде функций ввода, вывода и обработки массивов - C++
Здравствуйте народ,помогите в решении данной задачки с помощью подпрограммы: Дан массив из N элементов. Отсортировать по возрастанию...

Напишите функцию сортировки, похожую на функцию которая использовалась для сортировки массивов, с той разницей, что ее а - C++
Напишите функцию сортировки, похожую на функцию которая использовалась для сортировки массивов, с той разницей, что ее аргументом должен...

4
PointsEqual
ниначмуроФ
836 / 520 / 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) дополнительной памяти.
3
MILAN
886 / 780 / 86
Регистрация: 21.02.2009
Сообщений: 1,722
04.10.2010, 23:30 #3
Алгоритмы сортировок
1
fasked
Эксперт С++
4945 / 2525 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
04.10.2010, 23:38 #4
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
$$RaMpAgE, разные сортировки оптимальны для разных наборов данных. Есть очень красивый ресурс, который показывает процесс сортировки крайних случаев, все анимированно и очень красиво.
7
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 сортировок, на мой взгляд, хватит, чтобы иметь общее представление о сортировках.

Для углубленного изучения можно рассмотреть Плавную сортировку. Она редко встречается. Но мне показалась довольно интересной с точки зрения реализации и понимания.
Описание Плавной сортировки с картинками можно посмотреть здесь
17.10.2010, 14:19
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.10.2010, 14:19
Привет! Вот еще темы с ответами:

Алгоритмы Сортировки - C++
помогите пожалуйста выполнить вот такое задание... завтра утром нужно сдать.... 1) Реализовать алгоритмы Insertion-Sort(сортировка...

алгоритмы сортировки - C++
нужно выполнить сортировку массива целых чисел 3 методами: простыми включениями, простым выбором, простым обменом подскажите пожалуйста...

векторы и алгоритмы сортировки - C++
У меня есть алгоритм сортировки In-place merge sort, для обычных массивов любого типа данных. #include <iostream> #include <vector> ...

типовые алгоритмы сортировки - C++
типовые алгоритмы сортировки как они выглядят ?


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

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

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