Алгоритмы сортировки (часть 3)

Сортировки слиянием. Сортировка последовательностей.

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

Сортировка простым слиянием.

Сортировка слиянием - это алгоритм сортировки, который использует подход "разделяй и властвуй". Он разбивает массив на две половины, рекурсивно сортирует их, а затем объединяет отсортированные половины.

void merge(int* arr, int left, int mid, int right) {

int i, j, k;

int n1 = mid - left + 1; // Вычисляем размер левого подмассива

int n2 = right - mid; // Вычисляем размер правого подмассива

// Создаем временные массивы для хранения разделенных данных

int leftArray[n1], rightArray[n2];

// Копируем данные во временные массивы из исходного массива

for (i = 0; i < n1; i++) leftArray[i] = arr[left + i];

for (j = 0; j < n2; j++) rightArray[j] = arr[mid + 1 + j];

// Объединяем временные массивы в исходный массив

i = 0; // Индекс начала левого подмассива

j = 0; // Индекс начала правого подмассива

k = left; // Индекс начала объединенного массива

while (i < n1 && j < n2) {

if (leftArray[i] <= rightArray[j]) {

arr[k] = leftArray[i];

i++;

} else {

arr[k] = rightArray[j];

j++;

}

k++;

}

// Если остались элементы в левом подмассиве, копируем их

while (i < n1) {

arr[k] = leftArray[i];

i++;

k++;

}

// Если остались элементы в правом подмассиве, копируем их

while (j < n2) {

arr[k] = rightArray[j];

j++;

k++;

}

}

void mergeSort(int array[], int left, int right) {

if (left < right) {

// Находим середину массива для разделения на подмассивы

int mid = left + (right - left) / 2;

// Рекурсивно сортируем левую и правую части

mergeSort(array, left, mid);

mergeSort(array, mid + 1, right);

// Сливаем отсортированные части в один массив

merge(array, left, mid, right);

}

}

Алгоритм работает следующим образом:

1. Разделение: Массив рекурсивно делится пополам до тех пор, пока каждый подмассив не будет содержать только один элемент.

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

3. Конкатенация: Процесс слияния продолжается, пока все подмассивы не будут объединены в один отсортированный массив.

Этот алгоритм эффективен для больших наборов данных, поскольку его среднее и худшее время выполнения составляет O(n log n), где n - количество элементов в массиве.

Сортировка естественным слиянием.

Алгоритм естественного слияния - это метод сортировки, который использует стратегию "разделяй и властвуй". Он работает следующим образом:

1. Разделение: Входной массив разделяется на серии(естественные отсортированные последовательностей) подряд идущих отсортированных элементов, которые называются "естественными сериями".

2. Слияние: Серии сливаются попарно, пока не останется одна отсортированная серия, которая и будет являться отсортированным массивом.

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

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

void merge(int *array, int start, int middle, int end) {

// Создаем временный массив для хранения отсортированных элементов

int *tempArray = new int[end - start + 1];

int leftIndex = start, rightIndex = middle + 1, tempIndex = 0;

// Сливаем элементы во временный массив в отсортированном порядке

while (leftIndex <= middle && rightIndex <= end) {

if (array[leftIndex] <= array[rightIndex]) {

tempArray[tempIndex++] = array[leftIndex++];

} else {

tempArray[tempIndex++] = array[rightIndex++];

}

}

// Если остались элементы в левом подмассиве, добавляем их

while (leftIndex <= middle) {

tempArray[tempIndex++] = array[leftIndex++];

}

// Если остались элементы в правом подмассиве, добавляем их

while (rightIndex <= end) {

tempArray[tempIndex++] = array[rightIndex++];

}

// Копируем отсортированные элементы обратно в исходный массив

for (leftIndex = start, tempIndex = 0; leftIndex <= end; leftIndex++, tempIndex++) {

array[leftIndex] = tempArray[tempIndex];

}

// Освобождаем память временного массива

delete[] tempArray;

}

// Функция естественной сортировки слиянием

void naturalMergeSort(int *array, int size) {

bool isSorted = false;

// Повторяем до тех пор, пока массив не будет полностью отсортирован

while (!isSorted) {

isSorted = true;

int currentIndex = 0, nextIndex, mergeEndIndex;

// Проходим по всему массиву

while (currentIndex < size) {

// Находим конец первого отсортированного подмассива

nextIndex = currentIndex + 1;

while (nextIndex < size && array[nextIndex - 1] <= array[nextIndex]) {

nextIndex++;

}

// Находим конец второго отсортированного подмассива

mergeEndIndex = nextIndex;

while (mergeEndIndex < size && array[mergeEndIndex - 1] <= array[mergeEndIndex]) {

mergeEndIndex++;

}

// Если найден второй подмассив, выполняем слияние

if (mergeEndIndex < size) {

isSorted = false;

merge(array, currentIndex, nextIndex - 1, mergeEndIndex - 1);

}

// Переходим к следующему подмассиву

currentIndex = mergeEndIndex;

}

}

}