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

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

Войти
Регистрация
Восстановить пароль
 
artemed
129 / 0 / 1
Регистрация: 16.10.2012
Сообщений: 53
#1

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

15.03.2013, 00:19. Просмотров 925. Ответов 8
Метки нет (Все метки)

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

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

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

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

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

Так как же мне посчитать эти параметры С и М ?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.03.2013, 00:19     Выбор алгоритма сортировки
Посмотрите здесь:

Выбор оптимального алгоритма сортировки. - C++
Характеристика массива:отсортирован в случайном порядке. Необходимо подобрать метод сортировки по возрастанию и обосновать выбор.

Устойчивость алгоритма сортировки - C++
Добрый вечер, всех с прошедшими праздниками. Может кто-нибудь подсказать (по возможности помочь реализовать) алгоритм проверки устойчивости...

Реализация алгоритма сортировки вставками - C++
Мне нужно сделать лабу тема вверху... перед этим прочитал тему http://www.cyberforum.ru/cpp-beginners/thread27084.html все равно не...

Подсчёт время работы алгоритма сортировки - C++
Пытаюсь посчитать время работы алгоритма в миллисекундах, но постоянно выходит минусовое число. Как написать правильно? start_time =...

Реализация алгоритма быстрой сортировки quickSort - C++
это алгоритм быстрой сортировки quickSort прошу напишите значение строк файл исходного кода qs.cpp : #include "stdafx.h"...

Распараллеливание алгоритма сортировки - метод вставки - C++
Здравствуйте нужно осуществить распараллеливание алгоритма сортировки - метод вставки на N отдельных потоков. Есть идеи как это...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Юрий Владимиров
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
Эксперт С++
2892 / 1241 / 78
Регистрация: 27.05.2008
Сообщений: 3,353
07.06.2013, 12:37     Выбор алгоритма сортировки #3
Правильный ответ: любой. :-)

Потому что твоей формулировке - не задан критерий, по которому можно было бы считать, что один алгоритм "более подходит", чем другой.
Catstail
Модератор
22442 / 10847 / 1765
Регистрация: 12.02.2012
Сообщений: 17,962
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++
пожалуйстаааааа:cry:

Реализация алгоритма сортировки для любых типов данных - C++
Помогите пожалуйста переделать реализацию сортировки так, чтобы она могла работать с любыми типами данных(int, double, etc) Т.е. могла...

Время выполнения рекурсивного и итерационного алгоритма быстрой сортировки - C++
Почему вот это : void sort(int *ar, int L, int R){ int i, j, x, buf; x = ar; i = L; j = R; do { ...

Написать программу для реализации алгоритма сортировки методом пирамиды - C++
Разработать программу для реализации алгоритма сортировки методом пирамиды. Вывести в диалоге столбчатую диаграмму зависимости времени...


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

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

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

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