Т е о р е т и ч е с к и е с в е д е н и я

Временная сложность (ВС) алгоритма — это зависимость времени выполнения алгоритма от количества обрабатываемых входных данных. Здесь представляет интерес среднее и худшее время выполнения алгоритма. ВС можно установить с различной точностью. Наиболее точной оценкой является аналитическое выражение для функции: t = t(N), где t — время, N — количество входных данных (размерность). Данная функция называется функцией временной сложности (ФВС).

Например: t = 5N² + 6N + 1. Такая оценка может быть сделана только для конкретной реализации алгоритма в конкретной вычислительной системе. Математическая запись, позволяющая не учитывать эти условия, называется О-нотацией, предложенная П. Бахманом в 1892 г. Она определяется следующим образом:

если f(N) и g(N) есть функции, определенные в пространстве положительных целых чисел, тогда запись

f(N) = О(g(N))

(читается f(N) есть О большое от g(N)) обозначает, что существует такая константа с, что для всех достаточно больших положительных целых N | f(N)| ≤ с|g(N)|. При этих условиях можно также сказать, что «f(N) имеет порядок не больший, чем g(N)» или «f(N) растет не быстрее, чем g(N)».

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

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

Формулировка задачи может быть записана следующим образом. Если даны элементы а₁, а₂ ,…, а_n, то сортировка означает перестановку этих элементов в массив а_к1, а_к2,…,а_кn, где при заданной функции упорядочения f справедливы отношения f(а_к1) £ f(а_к2) £ … £ f(а_кn). Обычно функция упорядочения f не вычисляется по какому-то специальному правилу, а является значением элемента.

Метод сортировки называется устойчивым, если относительный порядок элементов с одинаковыми значениями не меняется при сортировке; неустойчивым — в противном случае.

Методы сортировки, в зависимости от лежащего в их основе приема, можно разбить на три базовых класса:

1) сортировка включением;

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

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

Сортировка включением

Этот метод обычно используют игроки в карты. Элементы (карты) условно разделяются на готовую последовательность а₁,…, а_i-1 и входную последовательность а_i,…, а_n. На каждом шаге, начиная с i=2 и увеличивая i на единицу, берут 1-й элемент входной последовательности и передают его в готовую последовательность, вставляя на подходящее место.

Алгоритм сортировки включением

1. Запоминаем элемент, подлежащий вставке.

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

3. Вставляем элемент на освободившееся место. Пункты 1-3 выполняем для всех элементов массива, кроме первого.

При поиске подходящего места для элемента x удобно чередовать сравнения и пересылки, т. е. как бы «просеивать» x, сравнивая его с очередным элементом a[j] и либо вставляя x, либо пересылая a[j] вправо. Просеивание может быть закончено при двух различных условиях:

1) найден элемент а_i с ключом меньшим, чем ключ x;

2) достигнут левый конец готовой последовательности.

Пример.

Начальный массив	34
i = 2
i = 3
i = 4
i = 5
i = 6
i = 7

Анализ сортировки включением

Если первоначальный массив отсортирован, то на каждом просмотре делается только одно сравнение, так что эта сортировка имеет порядок O(N). Если массив первоначально отсортирован в обратном порядке, то данная сортировка имеет порядок O(N²), поскольку общее число сравнений равно 1 + 2 + 3 +... + (N – 2) + (N – 1) = (N – 1)×N / 2, что составляет O(N²). Чем ближе к отсортированному виду, тем более эффективной становится сортировка простыми вставками. Среднее число сравнений в сортировке простыми вставками также составляет O(N²).

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

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

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

1. Находим наименьший элемент в неупорядоченной части массива.

2. Меняем местами найденный элемент с тем, который соседствует с упорядоченной частью.

3. Пункты 1 и 2 выполняем, пока в неупорядоченной части имеется более одного элемента.

Пример.

Начальные значения
Проход 1						03
Проход 2		06
Проход 3						37
Проход 4					41
Проход 5							61
Проход 6						71
Проход 7

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

Анализ сортировки простым выбором

При сортировке простым выбором число сравнений ключей не зависит от их начального порядка. На первом просмотре выполняется N – 1 сравнение, на втором — N – 2 и т.д. Следовательно, общее число сравнений равно (N – 1) + (N – 2) + (N – 3) +... + 1 = N×(N – 1) / 2, что составляет O(N²).

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

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

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

Алгоритм сортировки обменом:

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

2. Пункт 1 повторяем n – 1 раз.

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

Пример.

Начальные значения
Проход 1
Проход 2
Проход 3
Проход 4
Проход 5
Проход 6
Проход 7

Анализ сортировки обменом

При использовании сортировки обменом число сравнений элементов не зависит от их начального порядка. На первом просмотре выполняется N – 1 сравнение, на втором — N – 2 и т.д. Следовательно, общее число сравнений равно (N – 1) + (N – 2) + (N – 3) +... + 1 = N×(N – 1) / 2, что составляет O(N²).

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

Улучшенная сортировка обменом 1

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

Анализ улучшенной сортировки обменом 1

Число сравнений для этого метода зависит от числа проходов, необходимых для сортировки. В худшем случае, когда массив упорядочен в обратном порядке, выполняется N – 1 проходов. На первом проходе выполняется N – 1 сравнение, на втором — N – 2 и т.д. Следовательно, общее число сравнений равно (N – 1) + (N – 2) + (N – 3) +... + 1 = N·(N – 1) / 2, что составляет O(N²). В этом случае выполняется максимальное число перестановок, что увеличивает время выполнения алгоритма.

В лучшем случае, когда массив уже упорядочен, потребуется всего один проход и N – 1 сравнение, что составляет O(N). Перестановки в этом случае не выполняются.

Улучшенная сортировка обменом 2

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

Анализ улучшенной сортировки обменом 2

Анализ улучшенной сортировки обменом 2 аналогичен анализу улучшенной сортировки обменом 1. Порядок функций ВС этих алгоритмов в лучшем и худшем случаях одинаковый.

Сортировка Шелла

Сортировка Шелла — это улучшенный метод сортировки вставками. Был предложен Д.Л. Шеллом в 1959 г. Рассмотрим этот метод на примере (см. ниже). При первом проходе группируются и сортируются элементы, отстоящие друг от друга на 5 позиций: (Х₁,Х₆), (Х_2,Х₇), (Х₃), (Х₄), (Х₅), т.е. выполняется сортировка массива с шагом 5; при втором проходе — элементы, отстоящие друг от друга на три позиции: (Х₁,Х₄,Х₇), (Х₂,Х₅), (Х₃,Х₆); при третьем — на 1 позицию.

Если некоторый массив частично отсортирован с использованием шага h, а затем сортируется с использованием меньшего шага, то массив остается частично отсортированным по шагу h, т.е. последующие частичные сортировки не нарушают результата предыдущих сортировок. Следующий шаг сортировки меньше предыдущего, а последний — равен 1.

Пример.

Начальные значения
Просмотр 1 Шаг 5
Просмотр 2 Шаг 3
Просмотр 3 Шаг 1
Упорядоченный массив

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

1. Определить количество проходов t и шаг сортировки на каждом проходе. Результат сохранить в массиве h.

2. На i-ом проходе (i=1,…,t) выполнить сортировку включением с шагом h(i).

Анализ сортировки Шелла

Поскольку первый в сортировке Шелла используемый шаг является большим, отдельные подмассивы достаточно малы по отношению к исходному. Таким образом, сортировка включением над этими подмассивами работает достаточно быстро — O(N²) (эффективно при малом N). Сортировка каждого подмассива приводит к тому, что весь массив становится ближе к отсортированному виду, что также делает эффективным использование сортировки включением. Так как массив становится более упорядоченным, то O(N) < порядок ФBC < O(N²).

Анализ сортировки Шелла математически сложен. В случае правильного выбора шагов порядок ФВС будет выглядеть как O(N^1.2). Д. Кнут предложил выбирать шаги из следующего ряда: 1, 4, 13, 40, 121, …, а вычислять их по формуле: h_{i – 1} = 3· h_i + 1; h_t = 1; t = [log ₃ N] – 1 (количество просмотров), где N — размерность исходного массива. Т.е. элементы должны быть взаимно простыми числами. Исходя из этого порядок сортировки может быть аппроксимирован величиной О(N(log ₂ N)).

Сортировка Хоара

Сортировка Хоара—лучший из известных до сего времени метод сортировки массивов. Он обладает столь блестящими характеристиками, что его автор Ч. Хоар назвал эту сортировку быстрой. Быстрая сортировка основана на том факте, что для достижения наибольшей эффективности желательно разбить массив на подмассивы и сортировать подмассивы меньшего размера.

Алгоритм быстрой обменной сортировки: