II. Метод стандартного обмена

Методы сортировок

I. Сортировка массивов

Является важным разделом вычислительной математики, т.к. занимает значительную часть времени работы ЭВМ. 25% времени расходуется на задачи сортировки, поэтому следует обратить внимание на эффективность работы программ сортировки. Нет алгоритма наилучшего в любом случае. Трудно даже решить, какой алгоритм будет лучшим в данном случае, т.к. эффективность зависит от множества факторов:

§ числа сортируемых элементов

§ до какой степени они уже отсортированы

§ каково распределение значений сортируемых элементов

§ каков объём обрабатываемых элементов

§ какова сложность алгоритма

§ каковы требования к занимаемой памяти

С отсортированными данными легче работать, чем с произвольно расположенными, их легко найти, обновить исключить, включить, слить воедино. На отсортированных данных легче определить:

§ Имеются ли пропущенные элементы

§ Удостоверится: все ли они проверены

§ Легче найти общие элементы отсортированных массивов и т.п.

Программы обработки данных работают более эффективно при упорядоченных данных (например списки по алфавиту и числах по возрастанию), как в файлах баз данных по индексу или по записям.

II. Метод стандартного обмена

Упорядочим массив по возрастанию

Суть метода состоит в следующем:

Начиная с первых двух элементов массива сравниваются последовательно и по парно все элементы этого массива. Если последующий больше предыдущего, то перестановка не требуется, а если меньше, то их следует поменять местами. В итоге МАХ-элемент, «как пузырёк», выталкивается в конец массива. Но одного просмотра массива мало, надо ещё (n-1) просмотреть все элементы с первого по n-ынй, а лучше по (n-i)-ый, где I - число уже сделанных просмотров. То, что цикл по i заканчивается не при n-1, а при n-i, увеличивает эффективность алгоритма по край не мере в два раза.

Рис. 1

Рис. 2

Таблица трассировки для одного прохождения по массиву (как на Рис. 2)

№	i	j	A(j)	A(j+1)	s	A
						5,4,1,2,3
						4,5,1,2,3
						4,1,5,2,3
						4,1,2,5,3
						4,1,2,3,5

Рис. 3

Оценка метода стандартного обмена

В качестве оценки-характеристики используется

А) С – МАХ число сравнений

Б) - среднее или ожидаемое число сравнений

(n-1) просмотров

Среднее = (n-1)/2 сравнений за просмотр т.е. »(n-1)(n-1)/2»n²/2

Плюсы:

· запоминающегося названия и простота.

· прост в реализации.

· не требует дополнительного места в памяти под свою копию

Минусы:

· медленный вид сортировки: время выполнения алгоритма: (N^2)/2

· по числу сравнений и перестановок относительно числа

сортируемых элементов(т.е. крайне неэффективной для больших объёмов информации).

Дата добавления: 2015-11-30