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

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

Восстановить пароль Регистрация
 
artemed
129 / 0 / 1
Регистрация: 16.10.2012
Сообщений: 53
15.03.2013, 00:19     Выбор алгоритма сортировки #1
Доброе время суток!
В универе дали вот такое задание
Предположим, что необходимо отсортировать массив, состоящий из нескольких «случайных» элементов и следующих за ними упорядоченных элементов. Какой из алгоритмов сортировок наиболее подходит для решения данной задачи?

Имеется в виду следующие алгоритмы сортировок:

1.Сортировка с помощью прямого включения
2.Сортировка с помощью прямого выбора
3.Пузырьковая сортировка
4.Шейкерная сортировка
5.Сортировка Шелла

Лично я остановился на сортировке прямого включения.
Но сомневаюсь.Думаю что улучшенная шейкерная (с запоминанием перестановок) справится с задачей не хуже.
У кого какие соображения будут,пожалуйста поделитесь.

в моих лекциях по этой теме написано следующее:
Эффективность алгоритмов сортировки массива можно оценить по таким критериям, как
число необходимых сравнений элементов (С) и
число перестановок элементов (М).

Так как же мне посчитать эти параметры С и М ?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Юрий Владимиров
 Аватар для Юрий Владимиров
51 / 51 / 2
Регистрация: 06.04.2013
Сообщений: 178
07.06.2013, 12:31     Выбор алгоритма сортировки #2
могут различать минимальное, среднее, или максимальное число сравнений ключей (C), и пересылок элементов массива (М)
вот к примеру, для сортировки методом прямого выбора:
Число перестановок минимально в случае изначально упорядоченных элементов и максимально, если первоначально они располагались в обратном порядке.
Mmin=3(n-1)
Mmax=n2/4+3(n-1)
Число сравнений С не зависит от начального порядка элементов.
С=(n2-n)/2

есть еще такое понятие, как число обменов. В этом алгоритме оно равняется n-1б т к в вложенном цикле мы только определяем мин элемент, а в внешнем делаем обмен между ячейками (т е мин элемент на 1 место, и туда, где был мин эл то значение, которое было на 1 месте)
CheshireCat
Эксперт С++
2907 / 1235 / 78
Регистрация: 27.05.2008
Сообщений: 3,308
07.06.2013, 12:37     Выбор алгоритма сортировки #3
Правильный ответ: любой. :-)

Потому что твоей формулировке - не задан критерий, по которому можно было бы считать, что один алгоритм "более подходит", чем другой.
Catstail
Модератор
 Аватар для Catstail
21492 / 10245 / 1670
Регистрация: 12.02.2012
Сообщений: 17,129
07.06.2013, 12:47     Выбор алгоритма сортировки #4
нет, не любой. Есть такая характеристика сортировки - естественность. Сортировка естественна, если частично отсортированный массив сортируется быстрее, чем неотсортированный. Из перечисленных таковой является только сортировка вставками.
Юрий Владимиров
 Аватар для Юрий Владимиров
51 / 51 / 2
Регистрация: 06.04.2013
Сообщений: 178
07.06.2013, 13:01     Выбор алгоритма сортировки #5
про такую характеристику не слышал, но интуитивно понимается, что эффективность прежде всего в скорости работы.

немного не по теме, но может вот подскажете что значит и как понимать Количество перестановок?

вот у меня сейчас задание определить M в сортировке методом прямого выбора, но я так понимал что это кол-во обменов? обменов это макс n-1, очевидно, как понять кол-во перестановок?

и еще: я добавил в алгоритм, что если текущий элемент не отличается от минимального то обмен не производить. Это засчитают, или это уже какой-то модифицированный метод, может препод придраться?
CheshireCat
07.06.2013, 13:09
  #6

Не по теме:

Catstail, в первоначальном посте никаких требований к "естественности" нет. Вообще никаких критериев нет.

Юрий Владимиров
 Аватар для Юрий Владимиров
51 / 51 / 2
Регистрация: 06.04.2013
Сообщений: 178
07.06.2013, 13:14     Выбор алгоритма сортировки #7
вообще-то есть предпосылка (подсказка):
"состоящий из нескольких «случайных» элементов и следующих за ними упорядоченных элементов" т. е. относительно структуры можно выбрать самый эффективный алгоритм.
HighPredator
07.06.2013, 13:15
  #8

Не по теме:

CheshireCat, простите что вмешиваюсь, но в первом посте сказано:

Цитата Сообщение от artemed Посмотреть сообщение
Предположим, что необходимо отсортировать массив, состоящий из нескольких «случайных» элементов и следующих за ними упорядоченных элементов. Какой из алгоритмов сортировок наиболее подходит для решения данной задачи?
Это подразумевает под собой поиск такого объективного критерия, согласно которому можно определить наиболее подходящий под условие. Естественность таковым является.

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.06.2013, 14:20     Выбор алгоритма сортировки
Еще ссылки по теме:

C++ Провести исследования быстродействия алгоритма сортировки для различного числа элементов в массиве
Написать программу для реализации алгоритма сортировки методом пирамиды C++
C++ Реализация алгоритма быстрой сортировки quickSort

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

Или воспользуйтесь поиском по форуму:
Catstail
Модератор
 Аватар для Catstail
21492 / 10245 / 1670
Регистрация: 12.02.2012
Сообщений: 17,129
07.06.2013, 14:20     Выбор алгоритма сортировки #9
Цитата Сообщение от CheshireCat Посмотреть сообщение
в первоначальном посте никаких требований к "естественности" нет.
- правильно. В этом и вопрос. Тот, кто знаком с темой, должен уметь выбрать правильный алгоритм. Для частично отсортированного, вставки - самое то!

А есть еще понятие "устойчивость" - сортировка устойчива, если она не переставляет одинаковые элементы. Сортировка вставками (и пузырьковая тоже) устойчивы. Вставки всем хороши, но производительность = O(n2)...
Yandex
Объявления
07.06.2013, 14:20     Выбор алгоритма сортировки
Ответ Создать тему
Опции темы

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