Практикум. Сортировка массивов. Оценка вычислительной сложности алгоритма

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

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

В качестве оценки производительности методов обычно используют функциональную зависимость времени работы программы от размерности исходного массива t(n). При анализе алгоритмов в первую очередь интерес представляет характер зависимости при достаточно больших значениях размерности задачи (п -»»).

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

t(n)

Urn -------- = const * 0.

n-w g(n)

Это обозначается как t(n) = 0[g(n)].

Например, для полинома f(n) = 2п4 - Зп3 + 5п - 6, порядком является полином п4, или f(n) = 0(п4), так как

2п4 - Зп3 + 5п - 6

lim ---------------------------- =2.

п—кю п4

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

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

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

На практике интересны методы сортировки, которые позволяют экономно использовать оперативную память, поэтому целесообразно рассмотреть только методы, не требующие использования дополнительных массивов. Такие методы в практике программирования называют прямыми. Самыми простыми из прямых методов являются:

• метод выбора;

• метод вставки;

• метод обменов (метод пузырька).

Рассмотрим эти методы на конкретном примере.

Пример 4.9. Разработать программу сортировки элементов массива А(п), где п < 20, используя метод выбора, метод вставки и метод обменов. Оценить эффективность применения указанных методов.

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

Сначала находим минимальный элемент массива. Найденный элемент меняем местами с первым элементом. Затем повторяем процесс с п-1 элемен-

Рис. 4.13. Сортировка выбором


тами, начиная со второго, потом с п-2 элементами, начиная с третьего и т.д. до тех пор, пока не останется один, самый большой элемент массива (рис. 4.13).

Алгоритм сортировки выбором приведен на рис. 4.14. Ниже приведен текст программы, реализующий данный алгоритм.

Program sorti;

Var a:array[1..2Q] of real; j, i, n, imin:integer; min:real;

Begin

Writeln(‘Beedume количество чисел n

<< | >>
Источник: Иванова Г.С. Основы программирования. 2002

Еще по теме Практикум. Сортировка массивов. Оценка вычислительной сложности алгоритма:

  1. 18.5. Права и обязанности держателя (обладателя) по работе с массивами персональных данных
  2. СЛОЖНОСТЬ КОГНИТИВНАЯ
  3. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  4. О.А. Акулов Н.В. Медведев. Информатика и вычислительная техника, 2005
  5. Могилев А. В.. Практикум по информатике, 2005
  6. 5.6.3. Сложность - первое условие прозренний
  7. АЛГОРИТМ
  8. АЛГОРИТМ УДАЧИ
  9. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  10. Степанов А. Н.. Архитектура вычислительных систем и компьютерных сетей, 2007
  11. А.П. Пятибратов, Л.П. Гудыно, А.А. Кириченко. Вычислительные машины, сети и телекоммуникационные системы, 2009
  12. СЛОЖНОСТЬ
  13. Сложность структуры организации.