ПОНЯТИЕ АЛГОРИТМА И ЕГО СВОЙСТВА

Классификация структур данных

Большинство современных языков программирования может реализовывать технологию «структурного программирования». В них применяется структурирование логики программы и используемых ею данных.

Принцип «структурирования данных» воплощается в типизации языка, т.е. наделении его развитой системой типов данных.

Структура данных – это форма хранения и представления информации.

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

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

1. Линейные

a. Массив

b. Список

c. Связанный список

d. Стек

e. Очередь

f. Хэш-таблица

2. Иерархические

a. Двоичные деревья

b. N-арные деревья

c. Иерархический список

3. Сетевые

a. Простой граф

b. Ориентированный граф

4. Табличные

a. Таблица реляционной базы данных

b. Двумерный массив

5. Файлы

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

Линейные структуры данных

Элемент линейной структуры характеризуется порядковым номером или индексом в линейной последовательности элементов.

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

Линейный массив.
Адрес (элемент(index)) = размер_ячейки * index.

Список – это динамическая линейная структура данных, в которой каждый элемент ссылается

a) только на предыдущий (однонаправленный линейный список),

b) либо на предыдущий и следующий за ним (двунаправленный линейный список).

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

Список.

Двунаправленный список.

Связанный список – это вариант обычного линейного списка, оптимизированный для операций добавления и удаления элементов. Оптимизация заключается в том, что элементы связанного списка не обязаны в памяти располагаться друг за другом. Порядок элементов определяется ссылкой на первый элемент (который не обязан быть в самом начале выделенной для списка памяти) и последовательностью ссылок на остальные элементы списка.

Связанный список.

Стек – это динамическая линейная структура данных, для которой определены всего две операции: добавление элемента в конец и удаление последнего элемента. Еще говорят, что стек реализует очередь LIFO (Last in, First Out) – последним пришел, первым вышел. Например, при выполнении программы, компьютер в случае необходимости вызвать некоторую функцию или метод сначала заносит указатель на место ее вызова в стек. Этот подход обеспечивает корректный возврат после завершения метода к инструкции, следующей после точки вызова. Такая структура данных

называется стеком вызовов подпрограмм.

Стек.

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

Очередь.

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

Сетевые структуры данных

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

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

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

Граф.

Ориентированный граф.

4. Табличные структуры данных

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

Табличные структуры данных.

5. Файлы

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

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

Сложность типовых операций при работе
с линейными структурами данных

Структуры данных оказывают существенное влияние на методы решения задач и сложность типовых алгоритмов. Можно привести оценки сложности основных операций с линейными структурами данных, таких как добавление, удаление и поиск элемента по индексу или ключу. Элементарными операциями, в данном случае, являются операции сравнения, перебора, вычисления адреса или перестановки элементов набора структуры данных. В сводной таблице, помимо верхней оценки сложности, также приведены соответствующие перечисленным структурам данных компоненты библиотеки BCL. Таким образом, основные линейные структуры данных уже есть в готовом виде и доступны всем разработчикам программного обеспечения на платформе Microsoft.NET Framework.

Структура	Вставка	Удаление	Поиск	Компонент BCL
Массив	-	-	O(1)	Базовый тип Array
Список	O(N)	O(N)	O(N)	List< T>
Связанный список	O(1)	O(1)	O(N)	LinkedList< T>
Стек	O(1) (добавление в конец)	O(1) (удаление последнего)	O(N)	Stack< T>
Очередь	O(1) (добавление в конец)	O(1) (удаление первого)	O(N)	Queue< T>
Хэш-таблица	O(1)	O(1)	O(1)	Dictionary< TKey, TValue

АЛГОРИТМЫ ПОИСКА

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

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

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

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

Общий алгоритм поиска ключа можно представить так.

1. Ввести исходный массив (ключей).

2. Повторять

ввести аргумент поиска и вывести результат

пока не надоест.

3. Закончить.

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

Наиболее распространенными являются три алгоритма поиска:

1) Линейный;

2) Дихотомический:

3) Интерполирующий.

1.1. Алгоритм линейного поиска

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

Уточненный алгоритм будет таким.

1. Ввести исходный массив (ключей).

2. Выполнять

2. 1. Ввести аргумент поиска (целое число);

2. 2. Если аргумент поиска больше или равен нулю,

2.2.1. Результат (номер в массиве, num) = - 1 (не найден, такого номера нет);

2.2.2. Для индекса массива (i) от 0 до Длина.массива

Если аргумент поиска = ключ[i],

номер в массиве (num) = i;

2.2.3. Если номер num = - 1,

вывести: «Такого ключа в массиве нет»,

Иначе

вывести: «Ключ найден под номером num».

пока будет аргумент поиска больше или равен нулю.

3. Закончить.

Обозначим массив ключей key, а аргумент поиска - arg. Тогда соответствующий фрагмент программы линейного поиска будет иметь вид, приведенный ниже.

public static void main (String[] args) {

Scanner sc=new Scanner(System.in);

int n;

System.out.print(" Введите количество элементов массива => " );

n=sc.nextInt();

System.out.println(" \tВведите элементы массива " );

int key[]=new int[n];

for (int i = 0; i < key.length; i++)

key[i]=sc.nextInt();

System.out.println(" \n Поиск ключа" );

do{

int arg, num;

System.out.println(" \n Введите аргумент поиска – искомый ключ" );

arg=sc.nextInt();

if (arg> =0){

num=-1;

for (int i = 1; i < key.length; i++)

if (arg==key [i])

num=i;

if (num =-1)

System.out.println(" Такого ключа нет" );

else

System.out.println(" Ключ найден под номером “+ num);

} while (arg> =0);

}

Основной недостаток алгоритма линейного поиска – большое время. При использовании оператора For для поиска ВСЕГДА выполняется ровно n операций сравнения, не зависимо от того, найден ключ или нет. Поэтому программа, обнаружив аргумент в начале массива, продолжает его просмотр до конца, т.е. выполняет бесполезную работу. Время поиска может быть существенно сокращено, если обеспечить его прекращение, когда ключ найден. При равномерном распределении элементов в таблице эталонов (ключей) среднее время поиска может стать пропорциональным величине n / 2.

Этого можно достичь, изменив пункт 2 в рассмотренном выше алгоритме следующим образом.

Ускорение линейного поиска

2. Выполнять

2. 1. Ввести аргумент поиска (целое число);

2. 2. Если аргумент поиска больше или равен нулю,

2.2.1. Результат (num) = - 1 (не найден);

2.2.2. Начальный индекс, i=0;

2.2.3. Пока (num=-1) и (i< =n – Длины.массива)

a) Если аргумент поиска = ключ[i],

номер в массиве (num) = i;

b) i=i + 1

2.2.4. Если номер num = - 1,

вывести: «Такого ключа в массиве нет»,

Иначе

вывести: «Ключ num найден».

пока будет аргумент поиска больше или равен нулю.

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

// Ускорение линейного поиска }

do{

int arg, num, i;

System.out.println(" \n Введите аргумент поиска – искомый ключ" );

arg=sc.nextInt();

if (arg> =0){

num=-1;

int i=0;

while ((num=-1) & & (i < key.length)) {

if (arg==key [i])

num=i;

i++;

}

if (num =-1)

System.out.println(" Такого ключа нет" );

else

System.out.println(" Ключ" +num+” найден“);

} while (arg> =0);

}

Трудоемкость (временная сложность) алгоритма линейного поиска определяется числом операций сравнения, выполняемых при просмотре таблицы эталонов. В лучшем случае количество таких операций равно 1, в худшем – n, а в среднем, если возможные значения ключей равновероятны, - n / 2. Таким образом, асимптотическая оценка О(n) = n.

АЛГОРИТМЫ СОРТИРОВКИ

3.1. Основные определения и классы алгоритмов

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

Мы рассмотрим наиболее распространенные алгоритмы сортировки для чисел, хотя они могут быть распространены на строки и списки элементов, о которых говорилось в общем определении.

1.1.1. Классификация алгоритмов сортировки

При классификации учитывают следующие основные характеристики алгоритмов.

1) Устойчивость (stability) — устойчивая сортировка не меняет взаимного расположения равных элементов.

1) Естественность поведения — эффективность метода при обработке уже упорядоченных или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту особенность входной последовательности и работает лучше.

2) Использование операции сравнения. Алгоритмы, применяющие для сортировки сравнение элементов между собой, называются основанными на сравнениях. Минимальная трудоемкость худшего случая для этих алгоритмов составляет O(n²), но они отличаются гибкостью применения. Для специальных случаев (типов данных) существуют более эффективные алгоритмы.

Ещё одним важным свойством алгоритма является сфера его применения. При этом различают два основных типа упорядочения.

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

2. Внешняя сортировка, которая применяется для запоминающих устройств большого объёма, с последовательным доступом (упорядочение файлов). При этом в каждый момент доступен только один элемент, а затраты на перемещение по сравнению с выборкой из оперативной памяти неоправданно велики. Это накладывает дополнительные ограничения на алгоритм и приводит к методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью. Их объём настолько велик, что не позволяет разместить информацию в ОЗУ.

К алгоритмам устойчивой сортировки относят следующие.

1. Сортировка пузырьком (англ. Bubble sort ) — сложность алгоритма: O(n²); для каждой пары индексов производится обмен, если элементы расположены не по порядку.

2. Сортировка перемешиванием (Шейкерная, Cocktail sort, bidirectional bubble sort) — сложность алгоритма: O(n²).

3. Сортировка вставками (Insertion sort) — сложность алгоритма: O(n²); определяют место элемента в упорядоченном списке и вставляют его туда.

4. Гномья сортировка — сложность алгоритма: O(n²); сочетает методы пузырьковой сортировки и вставками.

5. Блочная сортировка (Корзинная, Bucket sort) — сложность алгоритма: O(n); требуется O(k) дополнительной памяти и знание о природе сортируемых данных.

6. Сортировка подсчётом (Counting sort) — сложность алгоритма: O(n+k); требуется O(n+k) дополнительной памяти (существует три варианта).

7. Сортировка слиянием (Merge sort) — сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти; упорядочивают две половины списка отдельно (первую и вторую), а затем — сливают их воедино.

8. Сортировка с помощью двоичного дерева (англ. Tree sort) — сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти.

Алгоритмами неустойчивой сортировки являются следующие методы.

1. Сортировка выбором (Selection sort) — сложность алгоритма: O(n²); выполняется поиск наименьшего или наибольшего элемента и помещение его в начало или конец упорядоченного списка.

2. Сортировка Шелла (Shell sort) — сложность алгоритма: O(n log₂ n); попытка улучшить сортировку вставками.

3. Сортировка расчёской (Comb sort) — сложность алгоритма: O(n log n)

4. Пирамидальная сортировка (Сортировка кучи, Heapsort) — сложность алгоритма: O(n log n); список превращается в кучу, берется наибольший элемент и добавляется в конец списка.

5. Плавная сортировка (Smoothsort) — сложность алгоритма: O(n log n).

6. Быстрая сортировка (Quicksort), в варианте с минимальными затратами памяти сложность алгоритма: O(n log n) — среднее время, O(n²) — худший случай; широко известен как быстрейший из известных для упорядочения больших случайных списков; исходный набор данных разбивается на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй; затем алгоритм применяется рекурсивно к каждой половине. При использовании O(n) дополнительной памяти сортировка становится устойчивой.

7. Поразрядная сортировка — сложность алгоритма: O(n·k); требуется O(k) дополнительной памяти.

8. Сортировка перестановкой — O(n·n! ) — худшее время. Для каждой пары осуществляется проверка верного порядка и генерируются всевозможные перестановки исходного массива.

Рассмотрим наиболее распространенные алгоритмы сортировки. Причем, запишем словесные пошаговые алгоритмы, а программы составим на лабораторных работах.

1.2. Наиболее распространенные
простые алгоритмы внутренней сортировки (массивов)

Для определенности будем считать, что эти алгоритмы применяются к массивам целочисленных ключей вида

a[0], a[1], a[2], … a[n-1].

Их можно разделить на три основные категории:

1) Сортировка вставками;

2) Сортировка выбором и

3) Сортировка обменом.

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

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

Рассмотрим работу алгоритма на примере массива из 8 чисел.

Исходный массив 44 55 12 42 94 18 06 67

При i = 1 44 55 12 42 94 18 06 67

При i = 2 12 44 55 42 94 18 06 67

При i = 3 12 42 44 55 94 18 06 67

При i = 4 12 42 44 55 94 18 06 67

При i = 5 12 18 42 44 55 94 06 67

При i = 6 0612 18 42 44 55 94 67

При i = 7 0612 18 42 44 55 6794

Здесь последний элемент подмассива (с последним значением j) выделен жирным, а анализируемый элемент – подчеркнут.

Словесное описание алгоритма можно представить так.

Алгоритм простой сортировки вставками

1. Задать исходный массив А из n элементов.

2. Для i от 0 до n

2.1. Индекс элемента в конце массива j = i

2.2. Пока (j > 0) И (А_j_-₁ > A_i)

2.2.1. Сдвиг большего элемента, чтобы было место для вставки

А_j = А_j-₁

2.2.2. j = j - 1

2.3. Вставка j - го элемента на его место

А_j = A_i

3. Вывести массив А.

Число сравнений и пересылок в худшем случае пропорционально n², т.е. сложность алгоритма равна О(n²).

Время сортировки можно сократить, если учесть, что начальная часть массива (до индекса j) упорядочена. При этом точку вставки можно найти методом деления пополам диапазона индексов этой части (от 0 до j).

Алгоритм сортировки двоичными вставками

4. Задать исходный массив А из n элементов.

5. Для i от 0 до n

5.1. Вставляемый элемент х = A_i

5.2. Левая граница диапазона L = 0.

5.3. Правая граница диапазона R =i.

5.4. Пока (L< R)

5.4.1. Искомый индекс m = (L + R)/2

5.4.2. Если A_m ≤ x

L = m + 1

Иначе

R = m.

5.5. Перепись элементов на одну позицию в конец массива (освобождение места для вставки)

Для j от i до R + 1 с шагом -1

А_j = А_j-₁

5.6. Вставка последнего элемента

А_R= x

6. Вывести массив А.

Число сравнений и пересылок рассмотренным методом в худшем случае пропорционально n*log(n), т.е. сложность алгоритма равна О(n*log(n)).

1.2.2. Сортировка выбором

Этот метод – один из наиболее простых. Он требует выполнения n-1 просмотра массива. Вначале выбирают наименьший элемент и ставят его на место первого элемента массива. Эта операция выполняется для оставшихся n-1 ключей, затем – для (n-2)-х и т. д. Во время k-го просмотра выявляется наименьший элемент, который затем меняется местами с k-м.

Рассмотрим работу алгоритма на примере массива из 8 чисел, использованного в предыдущем примере.

Исходный массив 44 55 12 42 94 18 06 67

При i = 1 06 55 12 42 94 18 44 67

При i = 2 06 12 55 42 94 18 44 67

При i = 3 06 12 18 42 94 55 44 67

При i = 4 06 12 18 42 94 55 44 67

При i = 5 06 12 18 42 44 55 94 67

При i = 6 06 12 18 42 44 55 94 67

При i = 7 0612 18 42 44 55 6794

Здесь начальный элемент подмассива, в котором ищется минимум, выделен жирным, а минимальное значение в нем – подчеркнуто.

Алгоритм сортировки выбором

1. Задать массив А из n чисел.

2. Для k от0 до n-1

2.1. j = k

2.2. Для i от k + 1 до n-1

2.2.1. Если A_i< A_j,

j = i.

2.3. Если k ≠ j, то

Поменять местами A_k и A_j.

3. Вывести массив A.

4. Закончить.

Число сравнений и пересылок в худшем случае пропорционально n², т.е. сложность алгоритма равна О(n²), а в среднем - О(n*log(n)). Таким образом, сортировка выбором предпочтительнее метода вставок.

3.2.3. Сортировка обменом
(Пузырьковая сортировка)

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

1) элементы массива сравниваются попарно: первое со вторым; второе с третьим; i-тое – с (i+1) - вым;

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

За один такой просмотр массива при сортировке по возрастанию минимальный элемент «вытолкнется», по крайней мере, на одно место вверх (вперед), а максимальный – переместится в самый конец (вниз). Таким образом, минимальный элемент как легкий пузырек воздуха в жидкости постепенно «всплывает» вверх (в начало последовательности). Отсюда – название метода.

Рассмотрим работу алгоритма на примере массива из 8 чисел, использованного в предыдущих примерах.

Исходный массив 44 55 12 42 94 18 06 67

После просмотра 1 44 12 42 55 18 06 67 94

После просмотра 2 12 42 44 18 06 55 67 94

После просмотра 3 12 42 18 06 44 55 67 94

После просмотра 4 12 18 06 42 44 55 67 94

После просмотра 5 12 06 18 42 44 55 67 94

После просмотра 6 06 12 18 42 44 55 67 94

Из примера видно, что большие числа сразу оказываются на своем месте, т.е. глубину просмотра можно уменьшать, а индекс элемента изменять не до n-1, а до n - k. В нем последние числа, которые стоят на своем месте, выделены жирным шрифтом.

За n-1 просмотр произойдет полное упорядочение массива при любом исходном расположении элементов в нем.

Алгоритм сортировки Шелла

1. Задать массив А из n чисел.

2. Выполнять

2.1. d = n / 2.

2.2. Для i от 0 до n – d с шагом d

2.2.1. j = i.

2.2.2. x = A_i

2.2.3. Пока ( j ≥ d) (A[j] > A[j + d])

a) A[j] = A[j + d]

b) j = j – d.

2.3. d = d / 2.

Пока d > 0.

3. Вывести массив А.

В зависимости от начального значения и закона изменения расстояния d рассматриваемый метод может работать быстрее или медленнее. Так, если d является степенью 2 (64, 32, …, 2, 1), то до последнего прохода элементы с четными индексами никогда не сравниваются с теми, у которых индексы нечетные. Поэтому при последнем проходе возможны перемещения на большие расстояния.

В ряде работ предлагается задавать значение d, равным 2^k – 1, или сложнее, либо вычислять размеры подмассивов заранее и хранить их в виде массива значений d.

Анализ сортировки Шелла довольно сложен. Число сравнений и пересылок в худшем случае пропорционально n², т.е. его сложность равна О(n²), а в лучшем - О(n log n). Вообще рассмотренный метод эффективнее сортировки вставками, но уступает быстрой сортировке.

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

Метод был предложен английским программистом Хоором. Он использует тот факт, что число перестановок в массиве может резко сократиться, если менять местами элементы, находящиеся на большом расстоянии. Алгоритм является разновидностью «пузырьковой» сортировки и реализует метод «разделяй и властвуй». Для этого обычно в середине массива выбирается один элемент (опорный). Далее слева от опорного располагают все элементы, меньше его, а справа – больше. Затем тот же прием применяют к половинкам массива. Процесс заканчивается, когда в частях массива останется по одному элементу.

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

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

Общий алгоритм можно представить так.

1. Из массива выбирается некоторый опорный элемент, например,

Опорный = a[n/2].

2. Запускается процедура разделения массива, которая перемещает все элементы, меньшие, либо равные Опорному, влево от него, а все, большие, или равные Опорному, - вправо.

3. Теперь массив состоит из двух подмассивов, причем длина левого меньше, либо равна длине правого.

4. Для обоих подмассивов, если в них больше двух элементов, рекурсивно заполняется та же процедура.

В конце получится полностью отсортированная последовательность.

ПОНЯТИЕ АЛГОРИТМА И ЕГО СВОЙСТВА

Алгоритм – это точное предписание о выполнении в определенном порядке некоторых операций, приводящих к решению всех задач данного класса.

Свойства алгоритма:

1) определенность (точность предписаний и однозначность результата);

2) массовость (ориентирован на класс задач, например решение системы произвольного количества уравнений при любых исходных данных);

3) дискретность (деление процесса решения на этапы, понятные человеку и ЭВМ);

4) результативность (результат должен быть обязательно – даже если его нет, должно быть сообщение об этом).

Способы описания алгоритмов (известны из курса «Программирование»):

1) словесный (описание действий, которые должны привести к решению задачи, например построение треугольника по трем его сторонам);

2) математический (в виде формул, например формула для нахождения корней квадратного уравнения);

3) графический (схемы алгоритмов);

4) на языке программирования.

Важнейшей характеристикой алгоритма и соответствующей ему программы является их сложность, которая может оцениваться:

a) временем решения задачи (трудоемкостью алгоритма);

b) требуемой емкостью памяти.

Наиболее часто сложность алгоритма оценивают по порядку величины (порядка n, n² и т.д.). Этот метод применим как к временной, так и к емкостной сложности.

1. Оценка порядка (временная оценка)

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

1. Простое присваивание: а < -- b, будем считать ее сложность, равной 1;

2. Одномерная индексация a[i]: (адрес (a)+i*длина элемента), будем считать ее сложность, равной 2;

3. Арифметические операции: (*, /, -, +), будем считать ее сложность, равной 1;

4. Операции сравнения: a < b, будем считать ее сложность, равной 1;

5. Логические операции (l1) {or, and, not} (l2), будем считать ее сложность, равной 1;

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

1. Линейная конструкция из k последовательных блоков

Трудоемкость конструкции есть сумма трудоемкостей блоков, следующих друг за другом.

Θ =f₁+f₂+…+f_k,

где f_k – трудоемкость k-го блока.

2. Конструкция «Ветвление»

If (Условие) then

Операторы

else

Операторы.

Общая трудоемкость конструкции «Ветвление» требует анализа вероятности выполнения операторов, стоящих после «Then» (р) и «Else» (1-р) и определяется как:

Θ = f_thenp + f_else(1-p),

где f_then и f_else – трудоемкости соответствующих ветвей.

3. Конструкция «Цикл»

for (i=1; i< = n; i++){

Тело цикла}

После сведения этой конструкции к элементарным операциям ее трудоемкость определяется как:

Θ =1+3*n+n* f_цикла,

где f_цикла – сложность тела цикла,

n – число его повторений,

3* n – трудоемкость изменения параметра и проверки условия выполнения цикла.

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

Рассмотрим примеры анализа простых алгоритмов.

Пример 1. Задача суммирования элементов квадратной матрицы размерностью n* n.

SumM (A, n; Sum)
Sum < -- 0
For i < -- 1 to n
For j < -- 1 to n
Sum < -- Sum + A[i, j]
end for
Return (Sum)
End

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

Θ (n)=1+ f_{цикла по}_i = 1 + 1+ 3*n + n * f_{цикла по}_j =

1 + 1+ 3*n + n *(1+ 3*n + n *(2 + 2 + 1 + 1))

= 2 + 3n + n *(1 + 3n + 6 n) = 9n²+4 n +2. (1.1)

Пример 2. Задача поиска максимума в одномерном массиве.

MaxS (S, n; Max)
Max < -- S[1]
For i < -- 2 to n
if Max < S[i]
then Max < -- S[i]
end for
return Max
End

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

1) Худший случай

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

Θ _х(n)=1+1+3+ (n-1) (3+2+1)=6 n – 1. (1.2)

2) Лучший случай

Минимальное количество переприсваиваний максимума (ни одного на каждом проходе цикла) будет в том случае, если максимальный элемент расположен на первом месте в массиве. При этом трудоемкость алгоритма будет равна:

Θ _л (n)=1+1+3+ (n-1) (3+2)=5 n. (1.3)

3) Средний случай

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

12 3 4 5 6 Следующая ⇒