Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.53/101: Рейтинг темы: голосов - 101, средняя оценка - 4.53
1 / 1 / 1
Регистрация: 04.10.2010
Сообщений: 17
1

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

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

Всем привет, хочу для общего развития узнать все способы сортировки массивов.(массив произвольный)
(метод пузырька я знаю)
какой из них самый быстрый?
я только начинаю учить С++ , поэтому прошу что бы программы выглядили попроще для понимания
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
04.10.2010, 23:27
Ответы с готовыми решениями:

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

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

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

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

4
ниначмуроФ
847 / 531 / 110
Регистрация: 12.10.2009
Сообщений: 1,913
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
897 / 791 / 186
Регистрация: 21.02.2009
Сообщений: 1,722
04.10.2010, 23:30 3
Алгоритмы сортировок
1
Эксперт С++
5027 / 2606 / 241
Регистрация: 07.10.2009
Сообщений: 4,310
Записей в блоге: 1
04.10.2010, 23:38 4
Лучший ответ Сообщение было отмечено как решение

Решение

$$RaMpAgE, разные сортировки оптимальны для разных наборов данных. Есть очень красивый ресурс, который показывает процесс сортировки крайних случаев, все анимированно и очень красиво.
7
UnderFelixAbove
17.10.2010, 14:19 5
Знать все сортировки может быть ни к чему. Важно понимать, что сортировки отличаются алгоритмической сложностью и их можно разбить на три класса в зависимости от уровня сложности (O(N*N), O(N*log(N)) и O(N)). Для каждого класса можно выбрать по две-три и досканально их изучить.
Среди квадратичных сортировок можно выделить:
1. Вставками
2. Выбором
Неплохой визуализатор можно поглядеть здесь: ссылка. Сортировку пузырьком не буду приводить в этом списке. Та же сортировка выбором пишется не дольше и для понимания не чуть не сложнее, не говоря уже о том, что работает она в два раза быстрее.

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

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

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

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

Для углубленного изучения можно рассмотреть Плавную сортировку. Она редко встречается. Но мне показалась довольно интересной с точки зрения реализации и понимания.
Описание Плавной сортировки с картинками можно посмотреть здесь
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
17.10.2010, 14:19

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

Написать две функции сортировки массива целых чисел, реализующих заданные алгоритмы сортировки – один из класса квадрат
#include <stdio.h> #include "stdafx.h" #include "iostream" #include <stdlib.h> #include...

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

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru