Сортировка многофазная

Сортировка многофазная

Многофазная сортировка основана на идее распределения начальных серий в соответствии с последовательностью чисел Фибоначчи. При этом процессе используется три последовательности: две входные и одна выходная. На каждой итерации элементы из двух входных последовательностей сливаются в третью. Когда одна из входных последовательностей заканчивается, она становится выходной. Слияние начинается с двух входных последовательностей, каждая из которых представляет серию длины 1. Далее эти серии объединяются, образуя серию длины 2, которая записывается в третью последовательность. Процесс слияния продолжается до того момента, пока все элементы из второй входной последовательности не будут использованы, после чего оставшиеся элементы из первой последовательности сливаются с соответствующими им сериями длины 2. Это приводит к появлению серий длины 3, которые затем помещаются во вторую последовательность. Далее серии длины 2 из второй последовательности переносятся в первую, и так далее. Такой процесс продолжается до тех пор, пока в первой последовательности не останется отсортированная последовательность.

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

Многофазная сортировка может быть более эффективной по сравнению с сбалансированной, так как она использует слияние ( n - 1 ) путей вместо ( n / 2 ), если начать с ( n ) последовательностей. Приблизительное количество необходимых проходов для сортировки равно ( log(N)n), где ( N ) - это количество последовательностей, а ( n ) - количество серий.

Для сбалансированного многопутевого слияния, общее количество проходов, необходимых для сортировки, пропорционально количеству серий, так как на каждом проходе происходит копирование всех данных. Один из способов уменьшить количество проходов - это распределение серий более чем между двумя последовательностями. Слияние ( r ) серий, равномерно распределенных между ( n ) последовательностями, приведет к ( r / N ) сериям после первого прохода. После второго прохода количество серий уменьшится до ( (r / N)^2 ), и так далее до ( (r / N)^k ) после ( k )-го прохода. Таким образом, общее количество проходов для сортировки ( n ) элементов с помощью ( n )-путевого слияния равно ( k = log_{n}(N) ). Поскольку на каждом проходе выполняется ( n ) операций копирования, то в худшем случае потребуется ( M = n *log_{n}(N) ) операций.

#include <iostream>

#include <queue>

using namespace std;

// Функция для слияния нескольких отсортированных последовательностей

void multiwayMerge(int** sequences, int* sequenceSizes, int numSequences, int*& output, int& outputSize) {

// Создаем минимальную кучу для отслеживания минимального элемента

auto comp = sequences {

return sequences[a.first][a.second] > sequences[b.first][b.second];

};

priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(comp)> minHeap(comp);

// Инициализируем кучу первыми элементами каждой последовательности

for (int i = 0; i < numSequences; ++i) {

if (sequenceSizes[i] > 0) {

minHeap.push({i, 0});

}

}

// Подсчитываем общий размер выходного массива

outputSize = 0;

for (int i = 0; i < numSequences; ++i) {

outputSize += sequenceSizes[i];

}

// Выделяем память для выходного массива

output = new int[outputSize];

int index = 0;

// Сливаем элементы, пока куча не станет пустой

while (!minHeap.empty()) {

auto [seqIndex, elemIndex] = minHeap.top();

minHeap.pop();

output[index++] = sequences[seqIndex][elemIndex];

// Если в последовательности есть еще элементы, добавляем следующий в кучу

if (elemIndex + 1 < sequenceSizes[seqIndex]) {

minHeap.push({seqIndex, elemIndex + 1});

}

}

}

Деревья

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

Основные свойства деревьев данных в информатике:

Иерархическая структура. Каждый узел имеет родительский узел и ноль или более дочерних узлов.

Один корневой узел. Он является вершиной дерева и не имеет родительского узла.

Уникальные пути. Каждый узел имеет уникальный путь от корневого узла до него.

Отсутствие циклов. Невозможно пройти по узлам и вернуться в исходный узел.

Рекурсивная структура. Каждый поддерево также является деревом данных.

Обход дерева - это процесс посещения каждого узла в дереве. Существуют разные стратегии обхода:

1.      Прямой обход (предупорядоченный): Сначала посещается корень, затем левое поддерево, и наконец правое поддерево.

2.      Обратный обход (подупорядоченный): Сначала посещаются все поддеревья, а затем корень.

3.      Симметричный обход: Сначала посещается левое поддерево, затем корень, и наконец правое поддерево.

4.      Обход в ширину: Узлы посещаются уровень за уровнем, каждый уровень обходится слева направо.

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

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