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

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

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

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

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

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

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

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

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

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

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

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

Реализовать три любых алгоритма сортировки матрицы на выбор - C++
Всем привет форумчане, сижу и ломаю голову над заданной задачей. А точнее как ее реализовать т.к в C++ не шарю. Помогит дельным советом...

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

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

Реализация алгоритма пузырьковой сортировки - C++
Задача на массивы, где нужно банки переливать (ну, у меня она с этим ассоциируется). Раньше решал где-то, но уже не помню где.

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

8
Юрий Владимиров
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 месте)
0
CheshireCat
Эксперт С++
2895 / 1244 / 78
Регистрация: 27.05.2008
Сообщений: 3,397
07.06.2013, 12:37 #3
Правильный ответ: любой. :-)

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

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

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

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

Не по теме:

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

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

Не по теме:

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

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

0
Catstail
Модератор
22838 / 11204 / 1812
Регистрация: 12.02.2012
Сообщений: 18,439
07.06.2013, 14:20 #9
Цитата Сообщение от CheshireCat Посмотреть сообщение
в первоначальном посте никаких требований к "естественности" нет.
- правильно. В этом и вопрос. Тот, кто знаком с темой, должен уметь выбрать правильный алгоритм. Для частично отсортированного, вставки - самое то!

А есть еще понятие "устойчивость" - сортировка устойчива, если она не переставляет одинаковые элементы. Сортировка вставками (и пузырьковая тоже) устойчивы. Вставки всем хороши, но производительность = O(n2)...
0
07.06.2013, 14:20
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.06.2013, 14:20
Привет! Вот еще темы с ответами:

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

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

Реализация алгоритма сортировки для любых типов данных - 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 { ...


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

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

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