РАЗДЕЛ 3. Структура данных и алгоритмы

⇐ ПредыдущаяСтр 8 из 69Следующая ⇒

1. Внутренняя сортировка данных. Простейшие алгоритмы сортировки: метод «пузырька», сортировка вставками, сортировка с помощью выбора. Временная сложность этих алгоритмов. Быстрая сортировка, оценка временной сложности в лучшем случае, в худшем случае и в среднем. Сравнение алгоритмов сортировки (простейших алгоритмов и быстрой сортировки), области их эффективного применения в зависимости от размерности задач.

Сортировка - это процесс упорядочения некоторого множества элементов, на котором определены отношения порядка >, <, > =, < = (по возрастанию ли убыванию).

Оценка алгоритмов сортировки

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

Рассмотрим параметры, по которым будет производиться оценка алгоритмов.

1. Число операций сортировки (сравнения и перемещения) -параметры, характеризующие быстродействие алгоритма.

2. Объем памяти – параметр, характеризующий использование алгоритмом дополнительной памяти.

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

- максимальную сложность, или сложность наиболее неблагоприятного случая, когда метод работает дольше всего;

- среднюю сложность - сложность метода в среднем (обычном) случае;

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

Алгоритмы могут иметь разную трудоемкость (количество операций с точностью до постоянного множителя), например, T(n2), T(n*log(n)), T(n). Минимальная сложность всякого алгоритма сортировки не может быть меньше T(n). Максимальная сложность метода, оперирующего сравнениями, не может быть меньше T(n*log(n)).

Рассмотрим временные сложности в порядке возрастания.

1. Сложность T(n).

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

2. Сложность T(n*log(n)).

Эта сложность получается, если на каждом шаге метода выполняется некоторое количество действий C*n, то есть зависящее от размера задачи прямо пропорционально, и задача размерности n сводится к задаче размерностью n/m, где m – целая положительная константа.

3. Сложность T(n²).

Такая сложность получается, когда мы имеем два вложенных цикла, число итераций, которых зависит от n прямо пропорционально. Или другими словами, на каждом шаге метода задача размерности n сводится к задаче размерности n-1, и при этом выполняется некоторое количество действий C*n, то есть зависящее от n прямо пропорционально.

Еще одним важным свойством алгоритма является его сфера применения. Здесь основных позиций две:

- внутренняя сортировка;

- внешняя сортировка.

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

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

Внешняя сортировка оперирует с запоминающими устройствами большого объема.

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

Сортировка методом «пузырька»

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

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

Для алгоритма пузырьковой сортировки количество выполняемых сравнений всегда одинаково и равно ½ (n²-n), где n - количество сортируемых значений. В наилучшем случае (если список уже отсортирован) количество перестановок равно нулю. Количество перестановок в среднем и в худшем случаях равны соответственно:

В лучшем случае: 0, в среднем случае: 3/4(n²-n), в худшем случае: 3/2(n²-n)

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

Пример

Возьмём массив с числами «5 1 4 2 8» и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.

Первый проход:

( 5 1 4 2 8) ( 1 5 4 2 8), Здесь алгоритм сравнивает два первых элемента и меняет их местами.

(1 5 4 2 8) (1 4 5 2 8), Меняет местами, так как

(1 4 5 2 8) (1 4 2 5 8), Меняет местами, так как

(1 4 2 5 8 ) (1 4 2 5 8 ), Теперь, ввиду того, что элементы стоят на своих местах ( ), алгоритм не меняет их местами.

Второй проход:

( 1 4 2 5 8) ( 1 4 2 5 8)

(1 4 2 5 8) (1 2 4 5 8), Меняет местами, так как

(1 2 4 5 8) (1 2 4 5 8)

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

Третий проход:

( 1 2 4 5 8) ( 1 2 4 5 8)

(1 2 4 5 8) (1 2 4 5 8)

Теперь массив отсортирован и алгоритм может быть завершён.

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

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

Среднее, а также худшее число сравнений и перемещений оцениваются как T(n²), дополнительная память при этом не используется.

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

В лучшем случае: 2(n-1), в среднем случае: 1/4(n²+n), в худшем случае: ½ (n²+n).

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

Сортировка с помощью выбора

Шаги алгоритма: 1) находим минимальное значение в текущем списке; 2)производим обмен этого значения со значением на первой неотсортированной позиции; 3) сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы.

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

Сложность алгоритма: T(n²).

Для нахождения наименьшего элемента алгоритм совершает n-1 сравнений. С учетом того, что количество рассматриваемых на очередном шаге элементов уменьшается на единицу, общее количество операций: T(n²). Алгоритм не использует дополнительной памяти. Особенностью данного метода является то, что он требует всего лишь n перемещений элементов (n - размер массива) и в то же время n² операций сравнения. Отсюда можно сделать вывод, что этот метод можно применять в случае, когда затраты на перемещение элементов существенно выше, чем затраты на их сравнение.

Cортировка методом отбора тоже является n-квадратичным алгоритмом. Внешний цикл исполняется n-1 раз, а внутренний - n/2 раз. В результате сортировка методом отбора требует ½ (n²-n) сравнений, что сильно замедляет работу при большом количестве элементов. Количества перестановок, требующиеся в наилучшем и наихудшем случаях для метода сортировки отбором, будут следующими:

В лучшем случае: 3(n-1), худшем случае: 1/4n²+3(n-1)

В наилучшем случае, если список уже упорядочен, требуется сравнить только (n-1) элемент, и каждое сравнение требует трех промежуточных шагов. Наихудший случай аппроксимирует количество сравнений. Средний случай вычисляется по следующей формуле: n(log n + y), где y - константа Эйлера, примерно равная 0.577216.

Хотя количество сравнений для пузырьковой сортировки и сортировки методом отбора одинаковы, однако, для сортировки отбором показатель количества перестановок в среднем случае намного лучше. Тем не менее, существуют еще более совершенные методы сортировки.

Быстрая сортировка

Этому методу требуется O(n lg n) в среднем и O(n²) в худшем случае. К счастью, если принять адекватные предосторожности, наихудший случай крайне маловероятен. Быстрый поиск не является устойчивым. Кроме того, ему требуется стек, т.е. он не является и методом сортировки на месте.

Метод быстрой сортировки по своим показателям превосходит все остальные алгоритмы. В его основе лежит метод перестановок.

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

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

Среднее число выполняемых сравнений для алгоритма быстрой сортировки равно. Среднее количество перестановок приблизительно равно (n logn)/6. Эти числа существенно меньше, чем соответствующие показатели любого из раннее рассмотренных методов сортировки.

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

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

Интенсивность работы алгоритма основана на количестве сравнений и перестановок, которые он выполняет.

Простые алгоритмы сортировки применяются на маленьких массивах. Также они являются составной частью более сложных методов.

Алгоритмы сортировки имеют большое практическое применение. Их можно встретить почти везде, где речь идет об обработке и хранении больших объемов информации. Для многих задач сортировки бывает лучше использовать простые методы, чем более сложные алгоритмы.

2. Внешняя сортировка данных. Модель внешней сортировки, её особенности, определяющие «узкое» место процесса упорядочения данных во внешней памяти. Сортировка слиянием, оценка её временной сложности. Подходы к минимизации полного времени выполнения внешней сортировки.

Внешняя сортировка – это сортировка данных, которые расположены на внешних устройствах и не вмещающихся в оперативную память.

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

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

⇐ Предыдущая 3 4 5 6 789 10 11 12 Следующая ⇒