Автор очень ответственно и профессионально подходит к выполнению заказов. Большое спасибо!
Информация о работе
Подробнее о работе
Введение в ассемблер. Связь программ на языке высокого уровня и ассемблера. "Шейкерная" сортировка
- 4 страниц
- 2014 год
- 235 просмотров
- 0 покупок
Гарантия сервиса Автор24
Уникальность не ниже 50%
Фрагменты работ
"Шейкерная" сортировка.
Сортировка перемешиванием (англ. Cocktail sort) — разновидность пузырьковой сортировки. Анализируя метод пузырьковой сортировки, можно отметить два обстоятельства.
Во-первых, если при движении по части массива перестановки не происходят, то эта часть массива уже отсортирована и, следовательно, ее можно исключить из рассмотрения.
Во-вторых, при движении от конца массива к началу минимальный элемент “всплывает” на первую позицию, а максимальный элемент сдвигается только на одну позицию вправо.
Эти две идеи приводят к следующим модификациям в методе пузырьковой сортировки. Границы рабочей части массива (т.е. части массива, где происходит движение) устанавливаются в месте последнего обмена на каждой итерации. Массив просматривается поочередно справа налево и слева направо.
Лучший случай для этой сортировки — отсортированный массив (O(n)), худший — отсортированный в обратном порядке (O(n^2)).
Наименьшее число сравнений в алгоритме Шейкер-сортировки C = N-1. Это соответствует единственному проходу по упорядоченному массиву (лучший случай)
Образно алгоритм можно описать так: на каждом шаге основного цикла рассматривается массив a[Left]÷a[Right], после выполнения двух внутренних циклов минимальный и максимальный элемент в исходном массиве перетекают к краям, минимальный в — a[Left], максимальный — в a[Right]. Пусть максимальный элемент имеет индекс k, тогда массив можно изобразить так: a[Left],a[1],..,a[k-1],A[k],a[k+1],..,a[Right];После сравнения A[k] с a[k+1] значение A[k] перейдет в k+1-ую ячейку,после сравнения k+1-ой c k+2-ой – в k+2-eю,и так далее,пока он не сместится в крайне правое положение с индексом Right. Аналогично для минимального. После выполнения цикла по всем подмассивам он отсортируется.
Постановка задачи
Алгоритм
Исходный код
Программа, алгоритм и отчет. Все написанно на языке Assembler, C++. Проверено в Visual Studio.
Введение в ассемблер (набрать в Google)
Форма заказа новой работы
Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям
