русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Сортировка SortBubble (SortBall)


Дата добавления: 2013-12-23; просмотров: 809; Нарушение авторских прав


Сортировка SortMinMax

Сортировка SortMin (SortMax)

Методы сортировки за время порядка O(n2)

В ситуациях, когда приходится сортировать массивы небольшой размерности, разумно пользоваться простыми методами сортировки. Простые и естественные способы сортировки требуют, как правило, времени работы порядка . Эти методы сортируют массивы небольшой размерности быстрее, чем их соперники - более эффективные по порядку, но и более сложные методы сортировки. Но понятно, что у каждого из квадратичных методов сортировки есть свой предел - то максимальное значение n, после которого эффективные методы со сложностью начинают работать быстрее.

Рассмотрим алгоритмы сортировки с квадратичной сложностью, начиная с простейших, интуитивно понятных.

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

Эта сортировка является слегка улучшенным вариантом предыдущей сортировки, когда минимальный и максимальный элементы находятся одновременно. Они и меняются местами с первым и соответственно последним элементами текущей части массива. Повышение эффективности достигается за счет того, что одновременный поиск максимума и минимума можно выполнить быстрее, чем при раздельном их поиске.

Эти две вариации одного алгоритма сортировки относят к классу "обменных сортировок". В каждом алгоритме сортировки присутствуют операции сравнения элементов и обмена элементов. Но алгоритмы могут отличаться тем, какие операции превалируют в реализации алгоритма. В сортировках прямого выбора минимумами и максимумами обмен выполняется только после того, как сделан выбор нужного элемента, требующий многократных проверок. В обменных сортировках обмен элементов является основной операцией в процессе сортировки. И те и другие методы имеют свои достоинства и, соответственно, недостатки. Операции обмена обычно более дорогие (требуют больше времени), чем операции сравнения. В этом преимущество методов прямого выбора. Но в обменных сортировках за один проход не только один элемент становится на свое место, но и другие элементы стремятся занять свои места, что позволяет ускорить сортировку.



Идея алгоритма пузырьковой сортировки SortBubble, принадлежащей классу обменных сортировок, состоит в том, чтобы, начиная с конца массива, сравнивать два соседних элемента и, если нарушается упорядоченность, производить обмен элементами - более легкий элемент меняется местами со своим соседом. Очевидно, что при первом проходе массива минимальный элемент, как самый легкий всплывет наверх, подобно пузырьку воздуха, и станет на первое место. Важно то, что при этом будут всплывать, приближаясь к своим законным местам, и другие легкие элементы. Обменные сортировки хорошо работают на почти упорядоченных массивах. Достоинство алгоритма еще и в том, что он позволяет собрать важную информацию - на каждом проходе можно подсчитывать число обменов. Если оно равно 0, то массив уже упорядочен, и сортировку можно прекращать.

Алгоритм "тяжелого шарика" SortBall является симметричной вариацией пузырьковой сортировки. Работа начинается с начала массива, и в процессе обмена вниз опускаются тяжелые элементы, так что на первом проходе максимальный элемент станет на последнее место.



<== предыдущая лекция | следующая лекция ==>
Сортировка | Проекты


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Полезен материал? Поделись:

Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.002 сек.