Data Structures and Algorithms

Содержание

• Basic algorithms
• Sets
• Sorts
• Linked Lists
  1. Single Linked List
  2. Double Linked List
• HashTables
• Binary Tree
  1. Simple Binary Tree
  2. AVL tree
  3. Red-Black tree
• Graph
• Non-Recursive Merge and Quick sort

Базовые алгоритмы

В классе ASD реализованы базовые методы, отражающие некоторые основные моменты работы с алгоритмами.

Класс ASD содержит следующие методы:

1. Числа Фибоначчи (3 способа)

Числа Фибоначчи – это элементы числовой последовательности, которые определяются по формуле :

Способы задания n-го числа Фибоначчи.

• Рекурсивная процедура (Метод Fibo)

В данном методе происходит вызов функцией самой себя, тем самым формируется n-число Фибоначчи.

• Нерекурсивная процедура (Метод FiboR)

С помощью цикла for происходит сложение предыдущих чисел Фибоначчи. Изначально заданы: F1 = 1, F2 = 1, в отличии от рекурсивной версии.

• Метод с использованием массива (Метод FiboArray)

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

2. Конвертирование в соответствующую систему счисления

Метод IntConvert формирует конвертированное число в соответствии с элементом, взятым из алфавита Letters = "0123456789ABCDEF";

3. Конвертирование строки в число

Метод ConvertStringToInt преобразует строку в число с помощью класса Convert и встроенного метода ToInt32.

4. Нахождение наибольшего общего делителя

Метод NOD помогает сформировать наибольший общий делитель двух чисел с помощью цикла while.

5. Проверка числа на простоту

Метод BoolTestSimple с помощью цикла for происходит проверка всех делителей. В случае деления без остатка возвращается false, иначе – true.

6. Метод половинного деления для нахождения корней уравнения (Метод PolDel)

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

7. Поиск минимума функции на отрезке методом золотого сечения (Метод GoldMin)

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

Множества

Множество (set) представляет собой набор различных объектов, которые называются элементами. Множество можно описать путем явного перечисления его элементов в виде списка, заключенного в фигурные скобки. Они не могут содержать один и тот же элемент дважды; кроме того, элементы множества не упорядочены. Если объект x является элементом множества А, то говорят, что x принадлежит А. Два множества (A и B) равны, если они содержат одни и те же элементы.

Для выполнения данной работы мной был реализован обобщенный класс Set<T>, в котором параметр типа «T», реализует интерфейс «Icomparable».

Класс Set<T> содержит два конструктора (метод необходимый для инициализации экземпляра класса) с нижеперечисленными значениями.

Класс Set<T> принимает следующие значения:

public int size; // размер множества
public int count; // количество элементов в множестве
public T[] data; // массив данных для формирования конечного множества

Класс Set<T> содержит следующие методы и свойства:

1. public bool Contains (T el) // проверка на наличие элемента в множестве

2. public int GetIndex (T el) // получение индекса элемента множества

3. public void Add (T el) // добавление нового элемента в множество

4. public void Resize (int newsize) // изменение размера множества

5.  public bool RemoveInd (int index) // удаление элемента по индексу

6. public bool RemoveEL (T el) // удаление элемента по значению

7. public T GetElementByIndex (int i) // получение элемента множества по индексу

8. public T SetElementByIndex (int index, T newEl) // установка нового элемента по индексу

9. public static Set<T> Union (Set<T> s1, Set<T> s2) // объединение множеств

10. public static Set<T> Intersection (Set<T> s1, Set<T> s2) // пересечение множеств

11. public static Set<T> Addition (Set<T> s1, Set<T> s2) // дополнение множества

12. public List<Set<T>> SelectSets()  // получение набора множеств из последовательности элементов множества

13. public void Allsubsets(T[] list) // поиск всех подмножеств множества

14. public override string ToString() // преобразование object в строковое представление

Пересечением множеств А и В называется множество, обозначаемое А⋂В, состоящее из всех объектов, каждый из которых принадлежит обоим множествам А и В одновременно.

Объединением множеств А и В называется множество, обозначаемое А ∪В, состоящее из всех объектов, каждый из которых принадлежит хотя бы одному множеству А или В.

Дополнением множества А до множества B называется совокупность элементов множества B, которые не входят в множество A. Данное множество можно получить если произвести разность множеств А и B.

В классе Program создаются объект класса Set<T> и соответствующие примеры.

Сортировки

Сортировка — это упорядочивание набора однотипных данных по возрастанию или убыванию. При сортировке элементов в массиве выполняются две основных операции: сравнения элементов по ключу сортировки и пересылка элементов. Для выполнения данной работы мной был реализован класс MySort. В нем было реализовано множество различных методов (сортировок), где параметр типа «T» реализует интерфейс «Icomparable».

В классе MySort представлены следующие методы, разделенные по группам:

I) Алгоритмы сортировки, не основанные на сравнении

public static void CountSort(int[] arr) // сортировка подсчетом

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

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

1. Находим максимальный элемент заданного массива (max)
2. Инициализируем массив count длины max + 1 с всеми элементами, равными 0 (хранилище количества каждого элемента заданного массива)
3. Сохраняем количество каждого элемента в соответствующем индексе в count массиве
4. Находим кумулятивную сумму элементов массива count и там же сохраняем её
5. Находим индекс каждого элемента исходного массива в массиве count

   (кумулятивная сумма и массив count позволяют поместить элемент в правильную ячейку отсортированного массива)

   *разница между соседними элементами X и Y определяет количество элементов заданного массива равных индексу Y

   *уменьшение элемента массива count позволяет распределить заданные элементы в отсортированном порядке

public static void RadixSort(int[] arr) // цифровая сортировка

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

Соответствующий алгоритм можно описать следующим образом:

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

*Сортировка производится с помощью CountSort с доп. принимаемым аргументом (текущий разряд)

*Суть данного алгоритма заключается в последовательной перестановке чисел в исходном массиве (рисунок ниже)

public static void BucketSort(int[] arr) // карманная сортировка

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

Сегментная сортировка в основном полезна, когда входные данные равномерно распределены по диапазону.

1. Для начала необходимо разбить наш массив на блоки / корзины / карманы. Для удобства количество корзин = 10 (эквивалетно кол-ву чисел от 1 до 10)
2. Теперь распределяем элементы по корзинам. Распределение происходит по соответствию индекса корзины и первой цифры целого числа
3. После того как все элементы распределены, мы выполняем сортировку внутри каждой корзины и соединяем их в один массив по порядку их индексов.

*Элементы каждой корзины сортируются с использованием любого из стабильных алгоритмов сортировки

*В моей реализации предусмотрена сортировка чисел принадлежащих промежутку [0, 1) и [1, +∞). Для этого нужно найти максимальный элемент входного массива и >вычислить число разрядов, примем его за p. Тогда, для вычисления индекса корзины элемент домножается на число, равное кол-ву корзин, и после делится на 10^p.

*Для корректной работы необходимо, чтобы исходные элементы лежали в одном диапазоне

II) Алгоритмы сортировки, основанные на сравнении

public static void BubbleSort<T>(T[] arr) // пузырьковая сортировка

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

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

public static void SelectionSort<T>(T[] arr) // cортировка выбором

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

− Среди элементов массива выбирается элемент с наименьшим значением.

− Выбранный элемент меняется местами с первым элементом массива.

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

public static void InsertionSort<T>(T[] arr) // cортировка вставкой

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

− следующий элемент меньший, чем включаемый;

− достигнута права граница массива.

Ниже продемонстрирована работа данного алгоритма на последнем шаге сортировки. Выполнилось условие, что следующий элемент (4) меньше, чем включаемый (7) и произошел выход из цикла. Далее “указатель” достигает правой границы массива, что означает завершение процесса сортировки.

public static void ShakerSort<T>(T[] arr)  // шейкер сортировка (перемешиванием)

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

− условием завершения процесса сортировки считать отсутствие парных перестановок при очередном просмотре;

− сравнение пар элементов производить только до места последней перестановки: раз не было перестановок, значит дальше элементы упорядочены;

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

public static void ShellSort<T>(T[] arr) // cортировка Шелла

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

Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ: отсутствие потребности в памяти под стек; отсутствие деградации при неудачных наборах данных — быстрая сортировка легко деградирует до O(n²), что хуже, чем худшее гарантированное время для сортировки Шелла.

public static int BinSearch<T>(T[] arr, T el) // бинарный поиск

Поиск можно значительно ускорить, если массив упорядочен, например, по возрастанию. В этом случае чаще всего применяется метод деления пополам или бинарный поиск. Суть этого метода заключается в следующем. Сначала искомый элемент сравнивается со средним элементом массива. Если искомый элемент больше среднего, то поиск продолжается в правой части массива, если меньше среднего – то в левой части. При каждом сравнении из рассмотрения исключается половина элементов – не имеет смысла искать элемент больше среднего в левой части, содержащей меньшие значения. Максимальное число требующихся сравнений равно log2(N).

public static T[] QuickSort<T>(T[] arr, int minindex, int maxindex) // быстрая сортировка

public static int Partition<T>(T[] arr, int minindex, int maxindex) // метод для поиска разделяемого элемента в быстрой сортировке

Быстрая сортировка, подобно сортировке слиянием, применяет принцип "разделяй и властвуй". Ниже описан процесс сортировки массива А[р..r].

Разделение

Массив А[р..r] разбивается на два (возможно, пустых) подмассива A[p..q-1] и A[q+1..r], таких, что каждый элемент А[p..q-1] меньше или равен А[q], который, в свою очередь, не превышает любой элемент подмассива A[q+1..r]. Индекс q вычисляется в ходе процедуры разбиения.

Властвование

Подмассивы A[p..q-1] и A[q+1..r] сортируются с помощью рекурсивного вызова процедуры быстрой сортировки.

Комбинирование

Поскольку подмассивы сортируются на месте, для их объединения не требуются никакие действия, весь массив А[р..r] оказывается отсортированным.

Разбиение массива

Ключевой частью рассматриваемого алгоритма сортировки является процедура Partition, изменяющая порядок элементов подмассива А[р..r] иначе A[p..q-1] или A[q+1..r] без привлечения дополнительной памяти.

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

1. Выбираем в качестве опорного элемента последний элемент массива (pivot).

2. Располагаем слева элементы, которые меньше опорного элемента, а справа больше опорного элемента. Слева и справа мы получаем два подмассива.

3. Далее, повторяем это действие для полученных подмассивов снова и снова (рекурсивно), пока весь массив не будет отсортирован.

На схеме ниже продемонстрирован процесс данной сортировки на примере массива из 8 элементов.

public static T[] MergeSort<T>(T[] arr, int minindex, int maxindex) // сортировка слиянием

public static void Merge<T>(T[] arr, int minindex, int middleindex, int maxindex) // метод для слияния массивов

Подобно QuickSort, MergeSort является алгоритмом класса "Разделяй и властвуй". Он делит входной массив на две половины, вызывается рекурсивно от каждой из получившихся половин, а затем объединяет две отсортированные половины. Функцию Merge() будем использовать для слияния двух половин.

Алгоритм:

1. Определяем middleindex (индекс, по которому будет осуществляться разбиение).

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

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

4. Затем объединяем пары одноэлементных массивов в двухэлементные массивы, сохраняя их в процессе. Затем эти отсортированные пары объединяются в четырехэлементные массивы и так далее до тех пор, пока не будет получен исходный отсортированный массив.

public static T[] TimSort<T>(T[] arr)

Timsort — гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слиянием, опубликованный в 2002 году Тимом Петерсом. Основная идея алгоритма в том, что в реальном мире сортируемые массивы данных часто содержат в себе упорядоченные подмассивы. На таких данных Timsort существенно быстрее многих алгоритмов сортировки.

Изначально определяется RUN — минимальный размер упорядоченной последовательности. Определяется он на основе n , где n - размер сортируемого массива, исходя из того, что оно должно быть не сильно большим, поскольку к этой последовательности будет применён алгоритм сортировки вставками, иначе она будет неэффективна, а также не сильно маленьким, в таком случае придется много раз выполнять соединение множества частей, что увеличит время работы.

Экспериментально выяснено, что наиболее эффективно использовать размеры 32 или 64.

Алгоритм:

1. Делим исходный массив на подмассивы размерности RUN и сортируем каждый с помощью InsertionSort
2. Далее поочередно производим слияние всех полученных подмассивов размерности size = RUN (после данного шага получим набор подмассивов размерности 2*size)
3. Повторяем второй шаг с полученным набором, увеличив size в 2 раза, до тех пор, пока size не будет равен размеру исходного массива

*Слияние осуществляем с помощью вспомогательно метода MergeSort - Merge

В классе Program создаются объект класса MySort и соответствующие примеры.

Односвязные и двусвязные списки

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

I) Односвязные списки

Односвязный список (single linked list) представляет набор связанных узлов, каждый из которых хранит собственно данные и ссылку на следующий узел. Последний элемент списка указывает на NULL (отсутствие). Элемент, на который нет указателя, является первым (головным) элементом списка. Здесь ссылка в каждом узле указывает на следующий узел в списке. В односвязном списке можно передвигаться только в сторону конца списка.

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

Для реализации односвязного списка мной были созданы следующие классы:

1. class SingleNode<T> - обобщенный класс для создания данных об узле.

Класс принимает следующие значения и свойства:

public int Key { get; set; } // ключ узла
public T Value { get; set; } // значение узла
public SingleNode<T> Next { get; set; }  // ссылка на следующий узел

Класс также содержит два конструктора (пустой и с вышеперечисленными данными) и метод ToString() для преобразования данных об узле в строковое представление.

2. class SingleList<T> - обобщенный класс для создания методов односвязного списка.

Класс принимает следующие значения и свойства:

public int Count { get; set; } // свойство, определяющее количество узлов (элементов) в списке

SingleNode<T> head; // ссылка на головной (первый) узел

И методы:

public void AddHead(int k, T v) // добавление узла в начало (обновление head)

Ниже продемонстрирован процесс добавления нового узла в начало односвязного списка.

public void AddEnd(int k, T v) // добавление узла в конец (обновление Next у последнего узла)

Ниже продемонстрирован процесс добавления узла в конец односвязного списка.

public void RemoveHead() // удаление головного (первого) узла

public void RemoveEnd() // удаление последнего узла

public bool IsContainsByValue(T value) // проверка на наличие в списке узла с определенным значением

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

public SingleNode<T> FindByValue(T value) // поиск узла по значению

public SingleNode<T> FindByIndex(int index) // поиск узла по индексу (0,1,2,3…)

public SingleNode<T> FindByKey(int key) // поиск узла по ключу

Методы вставки:

public void InsertByBeforeValue(T select, int k, T v) // вставка нового узла перед выбранным узлом

public void InsertByAfterValue(T select, int k, T v) // вставка нового узла после выбранного узла

Процесс вставки нового узла ПОСЛЕ выбранного значения примерно соответствует вставке ПЕРЕД выбранным значением (продемонстрированным на схеме выше), отличие заключается лишь в формировании ссылок для узлов.

Методы удаления узлов:

public bool RemoveByValue(T value) // удаление узла по значению

public bool RemoveByIndex(int index) // удаление узла по индексу

public bool RemoveByKey(int key) // удаление узла по ключу

Идея удаления узла по выбранному значению/индексу/ключу продемонстрирована ниже. Отличие состоит в способе поиска удаляемого узла.

public void View() // метод для вывода данных об узлах (значение и ключ) 

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

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

II) Двусвязные списки

Двусвязные списки (Double Linked List) также представляют последовательность связанных узлов, однако теперь каждый узел хранит ссылку на следующий и на предыдущий элементы. Двунаправленность списка приходится учитывать при добавлении или удалении элемента, так как кроме ссылки на следующий элемент надо устанавливать и ссылку на предыдущий. Но в то же время у нас появляется возможность обходить список как от первого к последнему элементу, так и наоборот - от последнего к первому элементу. В остальном двусвязный список ничем не будет отличаться от односвязного списка.

Для реализации двусвязного списка мной были созданы следующие классы:

1. class DoubleNode<T> – обобщенный класс для создания данных об узле.

Класс принимает следующие значения и свойства:

public int Key { get; set; } // ключ узла
public T Value { get; set; } // значение (данные) узла
public DoubleNode<T> Next { get; set; }  // ссылка на следующий узел
public DoubleNode<T> Prev { get; set; } // ссылка на предыдущий узел

Класс также содержит два конструктора (пустой и с вышеперечисленными данными) и метод ToString() для преобразования данных об узле в строковое представление.

2. class DoubleList<T> – обобщенный класс для создания методов двусвязного списка.

Класс принимает следующие значения и свойства:

public int Count { get; set; } // количество узлов(элементов) в списке
DoubleNode<T> head;  // ссылка на головной (первый) узел
DoubleNode<T> tail; // ссылка на хвостовой (последний) узел

И методы:

public void AddHead(int k, T v) // добавление узла в начало (обновление head)

public void AddEnd(int k, T v) // добавление узла в конец (обновление tail)

public bool IsContainsByValue(T value) // проверка на наличие в списке узла с определенным значением

public void RemoveHead() // удаление головного (первого) узла

public void RemoveEnd() // удаление хвостового (последнего) узла

Идея удаления последнего элемента похожа на идею, представленную в методе RemoveHead. Отличие заключается в том, что узел удаляется справа и уже Next принимает значение NULL.

Методы удаления узлов:

public bool RemoveByValue(T value)

public bool RemoveByKey(int index)

public bool RemoveByIndex(int key)

Идея удаления узла по выбранному значению/индексу/ключу продемонстрирована ниже. Отличие состоит в способе поиска удаляемого узла.

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

public DoubleNode<T> FindByValue(T value) // поиск узла по значению

public DoubleNode<T> FindByKey(int key) // поиск узла по ключу

public DoubleNode<T> FindByIndex(int index) // поиск узла по индексу (0,1,2,3…)

Методы вставки:

public void InsertByAfterValue(T select, int k, T v) // вставка нового узла после выбранного узла

public void InsertByBeforeValue(T select, int k, T v) // вставка нового узла перед выбранным узломx

Процесс вставки нового узла ПОСЛЕ выбранного значения примерно соответствует вставке ПЕРЕД выбранным значением (продемонстрированным на схеме выше), отличие заключается лишь в формировании ссылок для узлов.

public void ViewForward() // метод для вывода данных об узлах (отображение двусвязного списка)
                          // (значение и ключ) при проходе по списку от начала до конца

public void ViewBack() // метод для вывода данных об узлах (отображение двусвязного списка)
                       // (значение и ключ) при проходе по списку от конца к началу 

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

Хеш – таблицы

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

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

Хеширование

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

Коллизия

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

1. Метод цепочек.

Каждая ячейка хеш-таблицы — это список значений. При возникновении коллизии, новое значение просто добавляется в список в ту же ячейку таблицы.

2. Открытая адресация

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

Для реализации хеш-таблиц мной было создано 2 класса:

1. HTarray – обобщенный класс для реализации хеш-таблиц на основе массивов (с использованием открытой адресации).

Класс принимает следующие значения:

public SingleNode<T>[] htArray; // массив, элемент которого создан на основе узла односвязного списка (содержит все значения)
public int[] active; // массив для активных (занятых) ячеек
public int Size; // размер хеш-таблицы (максимальное возможное количество ячеек)
public int Count; // количество всех элементов в хеш-таблицы

Класс HTarray содержит конструктор с вышеперечисленными значениями.

И методы:

public int HashCode(int key) // метод, возвращающий хеш-функцию (определяет индекс)

public void Add(int key, T value) // добавление нового элемента в свободную ячейку

public SingleNode<T> SearchByKey(int key) // поиска элемента по ключу

public int SearchIndex(int key) // поиск индекса ячейки по ключу

public void RemoveByKey(int key) // удаление элемента из ячейки по ключу

public void Resize(int newsize) // изменение размера хеш-таблицы.

public void View() // метод для отображения хеш-таблицы (вывод данных о ячейках)

2. HTlist – обобщенный класс для реализации хеш-таблиц на основе списков (с использованием метода цепочек).

Класс принимает следующие значения:

public List<SingleNode<T>>[] htLists; // массив списков, элемент которого создан на основе узла односвязного списка (содержит все значения)

public int Size; // размер хеш-таблицы (максимальное возможное количество ячеек)

public int Count; // количество всех элементов в хеш-таблицы.

Класс HTarray содержит конструктор с вышеперечисленными значениями.

И методы:

public int HashCode(int key) // метод, возвращающий хеш-функцию (определяет индекс)

public void Adds(int key, T value) // добавление нового элемента в любую ячейку

public void RemoveByKey(int key) // удаление элемента из ячейки по ключу

public void Resize(int newsize) // изменение размера хеш-таблицы

public SingleNode<T> SearchByKey(int key) // поиска элемента по ключу

public void View() // метод для отображения хеш-таблицы (вывод данных о ячейках)

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

Бинарное дерево

I) Обычное бинарное дерево

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

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

Бинарное дерево является упорядоченным (деревом, у которого для каждого узла Node значение левого дочернего узла меньше, чем значение в Node, а значение правого дочернего узла больше значения в Node). Если в дереве могут содержаться одинаковые значения, то программист сам должен определить, влево или вправо помещать значение, равное значению в родительском узле, то есть соответствующее строгое неравенство заменить на нестрогое.

Для реализации бинарных деревьев мной было создано 2 класса:

1. BinaryNode - обобщенный класс для создания данных об узле дерева.

Класс принимает следующие значения и свойства:

public int Key; // ключ узла.
public T Value; // значение узла.
public BinaryNode<T> Parent; // ссылка на родительный узел
public BinaryNode<T> Right; // ссылка на правый дочерний узел (правый потомок/наследник)
public BinaryNode<T> Left; // ссылка на левый дочерний узел (левый потомок/наследник)

Класс также содержит два конструктора (пустой и с вышеперечисленными данными) и метод ToString() для преобразования данных об узлах и их ссылках в строковое представление.

2. BinaryTree - обобщенный класс для создания бинарного дерева и его методов.

Класс принимает следующее значение и содержит конструктор:

public BinaryNode<T> root; // корень дерева

public BinaryTree() // инициализация корня дерева, то есть создание дерева

И методы:

public void AddNodeInThree(int k, T v) // добавление нового узла в дерево

Добавление происходит по одному из случаев:

1. Ключ добавляемого узла больше ключа корня, тогда идем в правую часть дерева.

2. Ключ добавляемого узла меньше ключа корня, тогда идем в левую часть дерева.

3. Ключ корня равен ключу добавляемого узла, тогда не добавляем узел.

public BinaryNode<T> Search(int k) // поиск узла по ключу

public bool DeleteNode(int key) // удаление узла

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

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

public BinaryNode<T> MinNode(BinaryNode<T> tmp) // поиск узла c минимальным значением ключа от указанной вершины

public BinaryNode<T> MaxNode(BinaryNode<T> tmp) // поиск узла c максимальным значением ключа от указанной вершины

public void ViewAscending(BinaryNode<T> tmp) // отображение бинарного дерева по возрастанию ключей

public void ViewDescending(BinaryNode<T> tmp) // отображение бинарного дерева по убыванию ключей

public void ViewOrder(BinaryNode<T> tmp) // отображение бинарного дерева 
                                         // (обход в прямом порядке, то есть от корня, пока не дойдем до листьев)

В классе Program создаются бинарные деревья, а также применяются соответствующие методы к ним.

II) AVL tree

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

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

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

АВЛ-дерево (AVL-Tree) — сбалансированное двоичное дерево поиска, в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

Дерево постоянно обновляется, поэтому после добавления и/или удаления элементов, необходимо проверять условие сбалансированности. Чтобы проверить условие, нужно посчитать разницу высот между левым и правым поддеревом для каждого узла, также его называют показателем баланса — balance factor.

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

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

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

1. Если balance factor == -2:
   1. Если balance factor > 0 для левого поддерева: нужен левый поворот (от корня левого поддерева) и затем правый поворот (от вершины с bf = -2).
   2. Иначе : правый поворот (от вершины с bf = -2).
2. Если balance factor == 2:
   1. Если balance factor < 0 для правого поддерева: нужен правый поворот (от корня правого поддерева) и затем левый поворот (от вершины с bf = 2).
   2. Иначе : левый поворот (от вершины с bf = 2).

Балансировка дерева правым и левым поворотом

Балансировка дерева большим правым поворотом

Балансировка дерева большим левым поворотом

Для реализации AVL дерева мной были созданы следующие классы:

1. AVLnode – обобщенный класс для создания данных об узле дерева.

Класс принимает следующие значения и свойства:

public int Key;
public T Value;
public AVLnode<T> Right;
public AVLnode<T> Left;

Класс также содержит два конструктора (пустой и с вышеперечисленными данными) и метод ToString() для преобразования данных об узлах и их ссылках в строковое представление.

2. AVLtree – обобщенный класс для создания АВЛ дерева и его методов.

Класс принимает следующее значение и содержит конструктор:

public AVLnode<T> root; // корень дерева

public AVLTree() // инициализация корня дерева, то есть создание дерева

И методы:

public static int getSubTreeHeight(AVLnode<T> node) // вычисление высоты поддерева

public static int bfactor(AVLnode<T> node) // показатель баланса

public AVLnode<T> LeftRotation(AVLnode<T> node) // левый поворот (возвращает новый корень для данного поддерева)

public AVLnode<T> RightRotation(AVLnode<T> node) // левый поворот (возвращает новый корень для данного поддерева)

public AVLnode<T> balance(AVLnode<T> node) // метод для балансировки дерева

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

Так как в процессе добавления вершины мы рассматриваем не более, чем O(h) вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составит O(logn) операций.

public void AddNode(int k, T v) // обычное добавление для визуализации работы поворотов

public void AddNodeInAVLtree(int k, T v)  // добавление узла с балансировкой

public AVLnode<T> Insert(AVLnode<T> cur, AVLnode<T> node) // вспомогательный метод, содержащий балансировку

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

Поиск ближайшей вершины может быть выполнен по краю поддерева, что сокращает сложность до O(log(N)).

public AVLnode<T> findmin(AVLnode<T> p) // поиск узла с минимальным ключом в дереве p 

public AVLnode<T> removemin(AVLnode<T> p) // удаление узла с минимальным ключом из дерева p

public void RemoveNode(int key) // удаление узла из АВЛ дерева с сохранением баланса

public AVLnode<T> Delete(AVLnode<T> node, int key) // вспомогательный метод, содержащий балансировку

public void View(AVLnode<T> tmp) // вывод авл дерева в прямом порядке + balance factor

В классе Program создаются бинарные деревья, а также применяются соответствующие методы к ним.

III) RED - BLACK tree

Красно-чёрное дерево (RBT — Red Black Tree) — это разновидность самобалансирующегося двоичного дерева поиска, каждый узел которого имеет дополнительный бит цвета (красный или черный).

Данное дерево обладает следующими обязательными свойствами:

1. Корень всегда черный.

2. Каждый узел либо красный, либо черный.

3. Каждый лист, не содержащий данные (фиктивный) — черный.

4. Если узел красный, то оба его сына — черные.

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

Высота красно-черного дерева, состоящего из N узлов, лежит в диапазоне от двоичного логарифма log(N+1) до 2 * log(N+1). Благодаря ограничениям на построение такого дерева, путь от корня до самого дальнего листа не более чем вдвое длиннее, чем до самого ближнего, и дерево примерно сбалансировано (не идеально сбалансированно, то есть не проходит условие балансировки AVL-дерева).

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

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

После вставки или удаления требуется операция перекраски, требующая (O(log n) или O(1)) смен цветов (что на практике довольно быстро) и требует не более чем трёх поворотов дерева (для вставки — не более двух). Хотя вставка и удаление сложны, их сложность остается O(log n).

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

Пояснения, необходимые для описания алгоритмов :

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

«Дядя» — дочерний узел «Прародителя», то есть узел находящийся на уровень выше рассматриваемого узла в противоположной части дерева.

Балансировка при вставке

Алгоритм вставки точно такой же, как и при вставке в BST. Вставляем новый элемент с нулевыми потомками и красным цветом. Если отец нового элемента черный, то никакое из свойств дерева не нарушено. Если же он красный, то нарушается свойство 4, для исправления достаточно рассмотреть два случая:

1. Дядя этого узла тоже красный. Тогда, чтобы сохранить свойства 4 и 5, просто перекрашиваем родителя и дядю в чёрный цвет, а прародителя — в красный. В таком случае черная высота в этом поддереве одинакова для всех листьев, и у всех красных вершин родители черные. Проверяем, не нарушена ли балансировка (не нарушены свойства дерева перечисленные выше). Если в результате этих перекрашиваний мы дойдём до корня, то в нём в любом случае ставим чёрный цвет, чтобы дерево удовлетворяло свойству 3.

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

Балансировка при удалении ....

Графы

Графом G называется пара множеств (V, E), где E – произвольное подмножество из V (то есть V –конечное множество вершин, а Е — отношение на V). Элементы множеств V и E соответственно называются вершинами и ребрами графа G.

Если V1, V2 – вершины, а e = (v1, v2) – соединяющее их ребро, тогда вершина V1 и ребро e инцидентны, вершина v2 и ребро e тоже инцидентны. Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными

Различают два основных вида графов: ориентированные и неориентированные.

Граф G называется ориентированным графом (орграфом), если все его ребра являются ориентированными. Ориентированные ребра называют дугами. Дуга описывается как упорядоченная пара вершин (v, w), где вершину v называют началом, а w – концом дуги. Говорят, что дуга v → w ведет от вершины v к смежной с ней вершине w.

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

Графы обычно представлены тремя способами: матрица смежности, список смежности и матрица инцидеций.

Для реализации графов мной были созданы следующие классы:

1. Vertex – обобщенный класс для создания данных о вершине.

Класс принимает следующие значения и свойства:

public string Name { get; set; } // название вершины
public Vertex prevVertex; // предыдущая вершина (от которой пришли при обходе графа)
public double distance; // расстояние, которое прошли при посещении вершины
public List<Edge> AdjEdges; // набор смежных ребер
public ColorVertex color; // цвет вершины (для обхода в глубину и ширину)

Класс также содержит два конструктора (пустой и с вышеперечисленными данными), перечисление public enum для раскраски вершин и метод ToString() для преобразования данных о вершине в строковое представление.

2. Edge – обобщенный класс для создания данных о ребре.

Класс принимает следующие значения и свойства:

public Vertex From { get; set; } // откуда идет ребро
public Vertex To { get; set; } // куда идет ребро
public double Weight { get; set; } // вес ребра

Класс также содержит два конструктора (пустой и с вышеперечисленными данными), и метод ToString() для преобразования данных о ребре в строковое представление.

3. Graph – обобщенный класс для создания методов о графе.

Класс принимает следующие значения и свойства:

public List<Vertex> Vertices = new List<Vertex>() // список всех вершин графа
public List<Edge> AllEdges = new List<Edge>(); // список всех ребер графа
public int VertexCount { get { return Vertices.Count; } } // количество вершин графа
public int EdgeCount { get { return AllEdges.Count; } } // количество ребер графа

И методы:

public void AddVertex(Vertex vertex) // добавление вершины в граф

public bool AddEdge(Vertex from, Vertex to) // добавление ребра в граф

public void RemoveVertex(Vertex vertex) // удаление вершины в графе

public bool VertexIsContains(Vertex vertexName) // проверка графа на наличие вершины

public Vertex FindVertex(Vertex vertexName) // поиск вершины по названию вершины

public void View() // отображение графа

Обход графов.

Для отметки (посещения) применяется система раскрашивания вершин графа в один из трёх цветов: белый (white), серый (gray), чёрный (black). До обхода графа в глубину все его вершины «красятся» в белый цвет. При посещении вершины она приобретает серый цвет. А при возвратном прохождении через вершину она красится в чёрный. Посещать разрешается только белые вершины, серый цвет служит признаком прохождения вершины при обходе в глубину с последующим возвратом через неё.

public void BFS(Vertex startVertex) // поиск в ширину (обход графа)

Пусть выделена исходная вершина s. Алгоритм поиска в ширину систематически обходит все ребра для «открытия» всех вершин, достижимых из s, вычисляя при этом расстояние от s до каждой достижимой из вершины. Алгоритм работает как для ориентированных, так и для неориентированных графов. Поиск в ширину имеет такое название потому, что в процессе обхода мы идём вширь, то есть перед тем, как приступить к поиску вершин на расстоянии k+1, выполняется обход вершин на расстоянии k.

Ниже представлена схема обхода графа в ширину.

public void DFS(Vertex startVertex) // поиск в глубину (обход графа)

public void DFS_Visit(Vertex u) // вспомогательный метод DFS

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

Ниже представлена схема обхода графа в глубину.

public int GraphConnectivity() // связность графа

Данный метод основан на методе BFS.Изначально любой граф имеет 1 компоненту связи. Если после обхода остались не посещённые вершины (белые), счетчик увеличивается на единицу и обход совершается ещё раз.

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

Ниже продемонстрирован граф с 3-мя компонентами связи.

public void Dijkstra(Vertex startVertex)

Данный алгоритм позволяет найти кратчайшее расстояние от определенной вершины до всех других во взвешенном графе.

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

1. Присвоить каждой вершине графа начальную метку M[i] (distance) , равную какому-то очень большому числу (например бесконечности double.PositiveInfinity), символизирующему, что метка ещё никак не рассчитывалась. Исходной вершине (от которой совершаем обход) присвается значение равное 0, так как расстояние до самой себя равно 0. Исходная вершина принимается за текущую.
2. Для каждой вершины, смежной текущей вершине, корректируются метки: если M[i] > E[i] + MV[i], то M[i] = E[i] + MV[i], где M[i] - метка смежной вершины, MV[i] - значение метки текущей вершины, E[i] - вес ребра, инцидентного данным вершинам.
3. Текущая вершина помечается как окрашенная, алгоритм к ней больше не возвращается, а за новую текущую выбирается вершина с меньшим значением метки.
4. Пункты 2 и 3 повторяются, пока все вершины не будут окрашены.

Ниже продемонстрирована работа алгоритма Дейкстры с исходной вершиной 0:

В классе Program создаются графы, а также применяются соответствующие методы к ним.

Реализация QuickSort и MergeSort неркурсивным способом

В работе “Сортировки” крайне подробно изложен рекурсивный алгоритм быстрой сортировки и сортировки слиянием.
Для выполнения данной работы мной был создан обобщенный класс IndTask, в котором описаны следующие методы:

public static T[] QuickSortNR<T>(T[] arr, int minindex, int maxindex) // нерекурсивная быстрая сортировка

public static int partition<T>(T[] arr, int minindex, int maxindex)  // метод для поиска разделяемого элемента(pivot) 
                                                                     // в быстрой сортировке (вспомогательный метод)

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

Стек – один из видов разделения оперативной памяти. Его можно представить как стопку спичечных коробков, в каждой из которых лежат данные. Работа со стеком осуществляется по принципу LIFO (Last in – последний вошёл, First out – первый вышел, и никак иначе). Желая получить данные из стека, мы можем взять их только сверху и никогда из середины.

Данная реализация использует стек, заменяя рекурсивные вызовы помещением в стек параметров функции, а вызовы процедур и выходы из них — циклом, который осуществляет выборку параметров из стека и их обработку, пока стек не пуст. Мы помещаем “координаты” большего из двух подмассивов в стек первым с тем, чтобы максимальная глубина стека при сортировке N элементов не превосходила величины log(n).

Алгоритм работы:

1. Выбираем в качестве опорного элемента последний элемент массива (pivot).

2. Располагаем слева элементы, которые меньше опорного элемента, а справа больше опорного элемента. Слева и справа мы получаем два подмассива.

3. Помещаем координаты левого и правого подмассива в стек.

4. Пока стек не пустой, производим сортировку подмассивов.

   a. Повторяем действия из a и b снова и снова, пока правый и левый подмассивы не будут отсортированы.

   b. Получаем из стека координаты правого подмассива (производим сортировку, повторяя пункт 1 и 2).

   c. Получаем из стека координаты левого подмассива (производим сортировку, повторяя пункт 1 и 2).

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

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

public static T[] MergeSortNR<T>(T[] arr) // нерекурсивная сортировка слиянием (головной метод)

public static void MergePass<T>(T[] arr, int gap, int length) // метод для разбиения массива на части (вспомогательный метод)

В данном способе реализации рекурсию заменяет метод MergePass и переменная gap, увеличение которой происходит в головном методе MergeSortNR. С помощью цикла for и gap, в методе MergePass исходный массив разбивается на подмассивы одинакового размера (исключение в случае нечетного количества элементов в исходном массиве: последний подмассив состоит из 1-го элемента) и сразу же сортирует их. Далее, происходит увеличение gap в 2 раза, тем самым “разрыв” массива сокращается в 2 раза (осуществляется объединение полученных подмассивов). Эти действия повторяются снова и снова, пока не будет отсортирован весь массив. Процесс сортировки элементов в методе Merge остается неизменным по сравнению с рекурсивной версией.

Другими словами, gap – переменная разрыва, которая помогает формировать индексы для осуществления метода Merge, его максимальное значение – длина массива. Идея данной сортировки схожа с TimSort, отличие заключается в большем первоначальном разрыве (gap = 2 при первой итерации).

• minimal index = i;

• middle index = i + gap – 1;

• maximal index = length – 1.

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

Также был реализован вариант с использованием стека.

public static T[] MergeSortNR2<T>(T[] arr) // нерекурсивная сортировка слиянием (головной метод)

public static T[] Merge2<T>(T[] left, T[] right) // метод для слияния массивов (вспомогательный метод)

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

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

Ниже представлена схема, демонстрирующая алгоритм нерекурсивной сортировки слиянием с помощью стека.

В классе Program создаются объект класса IndTask и соответствующие примеры.