русс | укр

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

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

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

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


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

Сортировка за линейное время


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


За линейное время можно сортировать только массивы, на элементы которых наложены дополнительные ограничения: например, элементы принадлежат фиксированному числу видов.

8.5.1. Задача "Красные и белые"

В этой задаче элементы массива принадлежат двум видам - они либо красные, либо белые. Отсортировать такой массив можно за линейное время, более того, за один проход по массиву, выполняя не более одной проверки и одного обмена для каждого элемента массива. Задача разбиения массива на два подмножества в той или иной формулировке часто встречается в практике программирования. В частности, она возникает в алгоритме быстрой сортировки Хоара.

Все множество индексов элементов массива разделим на три непересекающихся подмножества: 0 - зона, содержащая только белые элементы; непроверенная зона для тех элементов, чей цвет не установлен; 1- зона для красных элементов. Инвариантом, поддерживаемым в проектируемом алгоритме, будет расположение зон. Массив отсортирован, когда непроверенная зона становится пустой. В этом идея алгоритма - поддерживать истинность инварианта, сокращая непроверенную зону. В начальном состоянии 0-зона и 1-зона пусты, а непроверенная зона занимает все множество индексов, так что ее начальная граница Start = 0, а граница Finish = n-1. В начальном состоянии инвариант считается истинным. Основной и единственный проход по циклу выполняется по непроверенной зоне до тех пор, пока эта зона не станет пустой (или не будет состоять из одного элемента). Проверка элементов начинается с левого конца непроверенной зоны. До тех пор, пока очередной элемент является белым, расширяется 0-зона и соответственно сокращается непроверенная зона - значение границы Start увеличивается на 1. В тот момент, когда встречается красный элемент, проверка прекращается и запускается аналогичный цикл, но теперь уже с правого конца непроверенной зоны. Когда на правом конце обнаруживается белый элемент, происходит обмен значениями на двух концах непроверенной зоны. Обмен восстанавливает истинность инварианта. По завершении цикла непроверенная зона становится пустой, так что 1-зона с красными элементами следует сразу за 0-зоной с белыми элементами и массив отсортирован.



8.5.2. Задача Дейкстры "О голландском национальном флаге"

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

Алгоритм сортировки за один проход по массиву нетрудно получить обобщением предыдущего алгоритма. Рассмотрим массив, состоящий из четырех зон: 0-зоны, содержащей только белые элементы, 1-зоны с синими элементами, непроверенной зоны и 2-зоны с красными элементами. Инвариантом, поддерживаемым в алгоритме, является расположение зон. В начальный момент все зоны, кроме непроверенной, пусты и инвариант считается истинным. Внешний цикл по-прежнему идет по элементам непроверенной зоны, продвигаясь попеременно то слева, то справа. При движении слева, пока встречаются синие элементы, расширяется синяя зона. Если встретился не синий элемент, то он может быть либо белым, либо красным. Если это белый элемент, то он меняется местами с первым элементом, начинающим синюю зону. После чего проверка продолжается с левого конца непроверенной зоны. Когда же встречается красный элемент, то непроверенная зона начинает проверяться с правого конца. Когда при проверке справа встречается не красный элемент, то происходит обмен с красным элементом, найденным при проверке слева. Если справа был обнаружен белый элемент, то понадобится еще один обмен, чтобы поставить его на свое место.

Все операции поддерживают истинность инварианта. Когда цикл завершается и непроверенная зона становится пустой, массив отсортирован.

8.5.3. Задача Гарри Поттера "Сортировочная шляпа"

Задачи, где в массиве 4 вида элементов, встречаются не менее часто. Например, молекула ДНК, как уже упоминалось, представляется строкой (массивом char) в алфавите из четырех символов. Этот массив иногда требуется отсортировать в некотором заданном порядке следования символов. Приведу следующую содержательную постановку этой задачи.

В школу чародейства и волшебства Хогвартс прибыли новые ученики числом N. Их посадили за один стол в произвольном порядке. Сортирующая шляпа рассортировала учеников и рассадила их по своим классам - слева направо: Гриффиндор, Рэйвенкло, Хаффлпафф, Слизерин.

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

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



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


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


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

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

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


 


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

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

 
 

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

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