Проекты

Задачи

Сортировка SortShell - улучшенный вариант сортировки вставками

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

Сортировка SortShaker

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

Сортировка вставками - это еще один класс простых методов сортировки. Рассмотрим простейший вариант этого способа сортировки. Чтобы описать идею алгоритма, предположим вначале, что массив уже упорядочен за исключением последнего элемента. Тогда задача сводится к тому, чтобы вставить этот элемент в нужную позицию. Это можно сделать двояко. Во-первых, можно применить алгоритм, подобный "пузырьку", выполняя обмен, пока последний элемент не "всплывет" на свое место. В лучшем случае не придется делать ни одного обмена, если последний элемент - это максимальный элемент и стоит уже на своем месте. В худшем случае придется сделать n сравнений и n обменов, если последний элемент - это минимальный элемент массива. В среднем - истина посредине. Другой способ состоит в том, чтобы воспользоваться упорядоченностью массива. В этом случае место вставки, используя алгоритм бинарного поиска, можно найти значительно быстрее за log(n) операций. К сожалению, нельзя избежать сдвига всех элементов массива ниже точки вставки.

Понятно, как распространить идею вставки на весь массив. Рассматриваем начальную часть массива, как уже упорядоченную. Поскольку часть массива, состоящая из одного первого элемента, упорядочена по определению, то вначале вставляем в эту упорядоченную часть второй элемент массива, затем третий, пока не дойдем до последнего.

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

В чем идея алгоритма сортировки Шелла? Зададим последовательность чисел:

Эта последовательность должна быть убывающей и заканчиваться значением . Любая последовательность чисел с такими свойствами является подходящей и гарантирует сортировку массива. До сих пор неизвестно, какая последовательность является наилучшей. Желательным свойством последовательности является взаимная простота чисел . Другое свойство требует, чтобы каждое из них примерно в два раза было меньше предыдущего. Хорошим выбором считается последовательность чисел, в которой . Первый член последовательности подбирается так, чтобы он был примерно равен n/2, где n - размерность массива. При n = 1000 последовательность может быть такой: 511, 255, 127, 63, 31, 15, 7, 3, 1.

Внешний цикл в сортировке Шелла - это цикл по последовательности . Каждый член этой последовательности делит элементы массива на группы, состоящие из элементов массива, отстоящих друг от друга на расстоянии . Для выбранной нами последовательности первый член последовательности создает большое число групп - групп, в каждой из которых не более двух элементов. На следующем шаге число групп уменьшается, а число элементов в них увеличивается. На последнем шаге при возникает одна группа, в которую входят все элементы. Суть алгоритма в том, что к каждой возникающей группе независимо применяется обычный алгоритм вставки, сортирующий каждую группу. В чем же суть алгоритма, ведь на последнем этапе ко всему массиву применяется обычный алгоритм вставки? За счет чего достигается эффективность алгоритма? Дело в том, что к последнему этапу массив будет "почти упорядочен", а на таких массивах алгоритм вставки работает крайне быстро. Действительно, если массив упорядочен, то алгоритм SortInsert c "пузырьковым обменом" выполнит всего лишь n операций сравнения и ему вообще не потребуются операции обмена.

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

/// <summary> /// Сортировка Шелла /// </summary> /// <param name="arr"></param> public static void ShellSort(T[] arr) { int n = arr.Length, m = (int)Math.Log(n); //Создать последовательность чисел Шелла - h int[] h = new int[m]; int t = 2; for (int i = 0; i < m; i++) { h[i] = t - 1; t *= 2; } //Внешний цикл по последовательности чисел h //Внутренний по числу групп for (int i = 0; i < m; i++) for (int j = 0; j < h[i]; j++) SortInsert(arr, n, h[i], j); } /// <summary> /// Сортировка вставкой группы элементов массива arr, /// начинающейся с элемента, который задан индексом ind, /// и отстоящих друг от друга на расстоянии h /// </summary> /// <param name="arr">массив</param> /// <param name="h">расстояние между элементами в группе</param> /// <param name="ind">индекс начального элемента группы</param> private static void SortInsert(T[] arr, int n, int h, int ind) { int k = ind + h, i = 0; T item; while (k < n) { //вставка arr[k] на место i = k - h; while (i >= ind) { if (arr[i+h].CompareTo(arr[i]) == -1) { item = arr[i]; arr[i] = arr[i + h]; arr[i + h] = item; i -= h; } else break; } k += h; } }

Заметьте, сортировка группы элементов, строящейся в методе Шелла, выделена в отдельную процедуру. Тем самым отделен процесс формирования группы от ее сортировки, что облегчает понимание алгоритма и обоснование его корректности. Для сортировки группы применяется метод сортировки вставкой, который, как отмечалось, эффективно работает для почти отсортированных групп. Несмотря на свою сложность, сортировка Шелла весьма эффективна и сравнима с быстрой сортировки Хоара. Считается, что временная сложность этой сортировки в среднем равна , что соответствует характеристикам лучших методов сортировки. Мои эксперименты на массивах различной длины от 10 до 10000 подтверждают высокую эффективность этого метода. На рис. 7.10 показаны результаты одного из экспериментов, где сравнивались времена четырех наиболее эффективных методов сортировки - быстрой сортировки Хоара, пирамидальной сортировки, сортировки слиянием и сортировки Шелла.

увеличить изображение
Рис. 7.10. Sort

51. Создайте DLL с сервисным классом ServiceSort, включающим методы сортировки SortMin, SortMax и метод HowLong, позволяющий оценить время сортировки. Постройте Windows-проект, поддерживающий работу с этой библиотекой классов.
52. Создайте DLL с сервисным классом ServiceSort, включающим методы сортировки SortMin, Sortmax, SortMinMax и метод HowLong, позволяющий оценить время сортировки. Постройте Windows-проект, поддерживающий работу с этой библиотекой классов.
53. Создайте DLL с сервисным классом ServiceSort, включающим методы сортировки SortBubble, SortBall и метод HowLong, позволяющий оценить время сортировки. Постройте Windows-проект, поддерживающий работу с этой библиотекой классов.
54. Создайте DLL с сервисным классом ServiceSort, включающим методы сортировки SortBubble, SortBall, SortShaker и метод HowLong, позволяющий оценить время сортировки. Постройте Windows-проект, поддерживающий работу с этой библиотекой классов.
55. Создайте DLL с сервисным классом ServiceSort, включающим методы сортировки SortBubble, SortInsert и метод HowLong, позволяющий оценить время сортировки. Постройте Windows-проект, поддерживающий работу с этой библиотекой классов.
56. Создайте DLL с сервисным классом ServiceSort, включающим метод сортировки SortBubble, SortShell и метод HowLong, позволяющий оценить время сортировки. Постройте Windows-проект, поддерживающий работу с этой библиотекой классов.
57. Создайте DLL с сервисным классом ServiceSort<T>, включающим методы сортировки SortMin, SortMax для массивов с произвольным типом элементов T, метод HowLong, позволяющий оценить время сортировки. Постройте Windows-проект, поддерживающий работу с этой библиотекой классов.
58. Создайте DLL с сервисным классом ServiceSort<T>, включающим методы сортировки SortMin, Sortmax, SortMinMax для массивов с произвольным типом элементов T, метод HowLong, позволяющий оценить время сортировки. Постройте Windows-проект, поддерживающий работу с этой библиотекой классов.
59. Создайте DLL с сервисным классом ServiceSort<T>, включающим методы сортировки SortBubble, SortBall для массивов с произвольным типом элементов T, метод HowLong, позволяющий оценить время сортировки. Постройте Windows-проект, поддерживающий работу с этой библиотекой классов.
60. Создайте DLL с сервисным классом ServiceSort<T>, включающим методы сортировки SortBubble, SortBall, SortShaker для массивов с произвольным типом элементов T, метод HowLong, позволяющий оценить время сортировки. Постройте Windows-проект, поддерживающий работу с этой библиотекой классов.
61. Создайте DLL с сервисным классом ServiceSort<T>, включающим методы сортировки SortBubble, SortInsert для массивов с произвольным типом элементов T, метод HowLong, позволяющий оценить время сортировки. Постройте Windows-проект, поддерживающий работу с этой библиотекой классов.
62. Создайте DLL с сервисным классом ServiceSort<T>, включающим метод сортировки SortBubble, SortShell для массивов с произвольным типом элементов T, метод HowLong, позволяющий оценить время сортировки. Постройте Windows-проект, поддерживающий работу с этой библиотекой классов.

63. Постройте класс ServiceSorting, содержащий методы сортировки и позволяющий анализировать время работы методов сортировки на одних и тех же массивах.
64. Постройте универсальный класс ServiceSorting<T>, содержащий методы сортировки массивов произвольного типа и позволяющий анализировать время работы методов сортировки на одних и тех же массивах.

8.4. Рекурсивные методы сортировки за время порядка O(n*log2(n))

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