Учебно-методическии комплекс дисциплины «Структуры и алгоритм обработки данных» (стр. 3 )

Сложность	Описание	Форма повторения
O(1)	Алгоритм константной сложности. Не зависит от количества элементов данных. Выполняется за постоянную единицу времени	Присваивание. Простое выражение. Алгоритм без цикла и рекурсии
Линейный. Сложность алгоритма пропорциональна размеру списка	Нахождение максимального элемента в массиве из n элементов
Квадратический	for (i=0; i<N; i++) for (j=0; j<N; j++) Простые алгоритмы сортировки
Кубический
Логарифмический	Возникает при неоднократном подразделении данных на подсписки. Бинарный поиск
NP - сложные (неполиномиальные). Частный случай - экспоненциальная сложность	Используются при неоднократном поиске дерева решений

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

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

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

Сортировкой, или упорядочиванием списка объектов, называется расположение этих объектов по возрастанию или убыванию согласно определенному линейному отношению порядка, такому, как отношение «?» для чисел.

Задача сортировки состоит в упорядочивании последовательности записей таким образом, чтобы значения ключевого поля составляли неубывающую последовательность. Другими словами, записи r1, r2, …, rn со значениями ключей k1, k2, …, kn надо расположить таком порядке, что. При этом записи с одинаковыми значениями ключей в упорядоченной последовательности располагаются рядом друг с другом.

Методы сортировки разделяют на две категории: сортировку массивов (внутренняя сортировка) и сортировку последовательных файлов (внешняя сортировка).

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

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

Сортировка посредством выбора

Предполагается, что n элементов данных хранятся в массиве А и по этому массиву выполняется n-1 проход. В нулевом проходе выбирается наименьший элемент, который затем меняется местами с А[0]. В следующем проходе просматривается неупорядоченная часть списка от элемента A[1], откуда выбирается наименьший элемент и запоминается в A[1]. Далее производится поиск наименьшего элемента в подсписке A[2] … A[n-1]. Найденное значение меняется местами с A[2]. Таким образом, выполняется n-1 проход, после чего неупорядоченный хвост списка сокращается до одного элемента, который и является наибольшим.

Пример:

Массив содержит целые числа 50, 20, 40, 75, 35.

	Проход 0: Выбрать 20. Поменять местами 20 и A[0]
Проход 1: Выбрать 35. Поменять местами 35 и A[1]
Проход 2: Выбрать 40. Поменять местами 40 и A[2]
Проход 3: Выбрать 50. Поменять местами 50 и A[3]
Отсортированный список

Вычислительная сложность

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

В i-ом проходе число сравнений с элементами A[i+1] … A[n-1] равно

(n-1) – (i+1) + 1 = n-i-1.

Общее число сравнений равно

.

Сложность алгоритма равна.

Сортировка обменом (сортировка методом пузырька)

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

Рассмотрим массив, расположенный вертикально. Каждый проход по массиву приводит к «всплыванию» пузырька на соответствующий его весу уровень.

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

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

Переменная ilast хранит последний участвующий в обмене индекс и приравнивается к нулю в начале каждого прохода. В нулевом проходе сравниваются соседние элементы. В каждой паре (A[i], A[i+1]) элементы меняются местами при условии, что A[i+1]<A[i], а значение ilast становится равным i. В конце этого прохода наибольшее значение оказывается в элементе A[n-1], а значение ilast показывает, что все элементы в хвостовой части списка от A[ilast+1] до A[n-1] отсортированы. В очередном проходе сравниваются соседние элементы в подсписке A[0] – A[ilast]. Процесс прекращается при ilast=0. Алгоритм совершает максимум n-1 проход.

Пример:

Рассмотрим пузырьковую сортировку на массиве из пяти целых чисел: 50, 20, 40, 75, 35.

Проход 0
	Поменять местами 50 и 20
Поменять местами 50 и 40
50 и 75 упорядочены
Поменять местами 75 и 35
75 – наибольший элемент. ilast = 3

Поскольку ilast не равен нулю, процесс продолжается. В проходе 1 сканируется подсписок от A[0] до A[3]=A[ilast]. Новым значением ilast становится 2.

Проход 1
	20 и 40 упорядочены
40 и 50 упорядочены
Поменять местами 50 и 35
50 – наибольший элемент. ilast = 2

В проходе 2 сканируется подсписок от A[0] до A[2] и элементы 40 и 35 меняются местами. Новым значением ilast становится 1.

Проход 2
	20 и 40 упорядочены
Поменять местами 40 и 35. ilast = 1

В проходе 3 выполняется единственное сравнение (20 и 35). Обменов нет, ilast=0, и процесс прекращается.

Проход 3
	20 и 35 упорядочены
Упорядоченный список. ilast = 0

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

Тогда можно еще улучшить алгоритм путем смены направлений следующих один за другим проходов. Этот алгоритм называется Шейкер-сортировкой.

Вычислительная сложность

В лучшем случае, кода массив уже упорядочен, производится всего один проход по списку. Тогда эффективность равна О(n).

В самом худшем случае необходимо выполнить все n-1 проходов, и в i-том проходе производится (n-i-1) сравнений.

Сложность наихудшего случая составляет.

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

Алгоритм Шейкер-сортировки выгоднее использовать в случае, когда известно, что элементы уже почти упорядочены.

Лекция №2

Тема: Сортировка вставками. Сортировка с разделением (быстрая сортировка). Слияние сортированных последовательностей.

Цель: привитие навыков использования методов сортировок при решении задач.

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

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

Пример:

Рассмотрим сортировку вставками на примере массива из пяти элементов А = 50, 20, 40, 75, 35.

Начать с элемента 50
Обработка 20	Вставить 20 в позицию 0; передвинуть 50 в позицию 1
Обработка 40	Вставить 40 в позицию 1; передвинуть 50 в позицию 2
Обработка 75	Вставить 75 в позицию 3
Обработка 35	Вставить 35 в позицию 1; сдвинуть хвост списка вправо

Элементы условно разделяются на готовую последовательность a[0],...,a[i-1] и входную последовательность a[i], ..., a[n-1].

На каждом шаге, начиная с i=1, берут i-й элемент входной последовательности и передают в готовую последовательность, вставляя его на подходящее место. По мере продвижения к началу списка каждый элемент сдвигается вправо (A[j]=A[j+1]).

Вычислительная сложность

Общее число сравнений составляет n(n-1)/2. В наилучшем случае, когда список уже отсортирован, сложность составляет O(n), в наихудшем случае - .

Сортировка бинарными вставками -

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