Может ли кто-нибудь объяснить на английском языке, как работает сортировка нерекурсивного слияния?
Спасибо
Нерекурсивная сортировка слияния
Ответ 1
Прокрутите элементы и сделайте каждую смежную группу из двух отсортированных путем замены их, когда это необходимо.
Теперь, имея дело с группами из двух групп (любые две, наиболее вероятные смежные группы, но вы можете использовать первую и последнюю группы) объединить их в одну группу, выбирая элемент с наименьшим значением из каждой группы, пока все 4 элемента не будут объединились в группу из 4. Теперь у вас есть только группы из 4 плюс возможный остаток. Используя цикл вокруг предыдущей логики, сделайте все это заново, за исключением того, что это время работает в группах по 4. Этот цикл работает до тех пор, пока не будет только одна группа.
Ответ 2
Нерекурсивная сортировка слияния, рассматривая размеры окна 1,2,4,8,16..2 ^ n над входным массивом. Для каждого окна ( "k" в коде ниже) все смежные пары окон объединяются во временное пространство, а затем возвращаются в массив.
Вот моя единственная функция, C-based, нерекурсивная сортировка слияния. Вход и выход находятся в 'a'. Временное хранение в 'b'. Однажды я хотел бы иметь версию, которая была на месте:
float a[50000000],b[50000000];
void mergesort (long num)
{
int rght, wid, rend;
int i,j,m,t;
for (int k=1; k < num; k *= 2 ) {
for (int left=0; left+k < num; left += k*2 ) {
rght = left + k;
rend = rght + k;
if (rend > num) rend = num;
m = left; i = left; j = rght;
while (i < rght && j < rend) {
if (a[i] <= a[j]) {
b[m] = a[i]; i++;
} else {
b[m] = a[j]; j++;
}
m++;
}
while (i < rght) {
b[m]=a[i];
i++; m++;
}
while (j < rend) {
b[m]=a[j];
j++; m++;
}
for (m=left; m < rend; m++) {
a[m] = b[m];
}
}
}
}
Кстати, также очень легко доказать, что это O (n log n). Внешняя петля над размером окна растет как мощность двух, поэтому k имеет log n итераций. В то время как есть много окон, покрытых внутренним циклом, вместе, все окна для данного k точно покрывают входной массив, поэтому внутренний цикл - O (n). Объединение внутренних и внешних циклов: O (n) * O (log n) = O (n log n).
Ответ 3
Цитата из Algorithmist:
Сорт слияния снизу вверх нерекурсивный вариант слияния sort, в котором массив сортируется по последовательность проходов. Во время каждого проход, массив делится на блоки размера m. (Первоначально m = 1). Каждые два смежных блока объединяются (как в обычной сортировке слияния), так и следующий проход делается с удвоенным размером значение m.
Ответ 4
И рекурсивная, и нерекурсивная сортировка слияния имеют одинаковую сложность O (nlog (n)). Это связано с тем, что оба подхода используют стек одним или другим способом.
В нерекурсивном подходе пользователь/программист определяет и использует стек
В рекурсивном подходе стек используется внутри системы для хранения обратного адреса функции, которая называется рекурсивно
Ответ 5
Основная причина, по которой вы хотите использовать нерекурсивный MergeSort, заключается в том, чтобы избежать рекурсии. Например, я пытаюсь сортировать 100 миллионов записей, каждая запись размером около 1 кбайт (= 100 гигабайт), в алфавитно-цифровом порядке. Сорт порядка (N ^ 2) будет занимать 10 ^ 16 операций, т.е. Для сравнения в течение одной операции потребуется всего десять минут. Порядок (N log (N)) Merge Sort займет менее 10 ^ 10 операций или менее часа, чтобы работать с одинаковой рабочей скоростью. Однако в рекурсивной версии MergeSort 100-миллиметровая сортировка элементов приводит к 50-миллионным рекурсивным вызовам MergeSort(). В нескольких сотнях байт на рекурсию в стеке это переполняет стек рекурсии, хотя процесс легко вписывается в кучную память. Выполнение сортировки слияния с использованием динамически распределенной памяти в куче. Я использую код, предоставленный Рамой Хетцлейном выше, но я использую динамически выделенную память в куче вместо использования стека. Я могу сортировать мои 100 миллионов записей с помощью нерекурсивная сортировка слияния, и я не переполняю стек. Соответствующий разговор для веб-сайта "Переполнение стека"!
PS: Спасибо за код, Рама Хетцлейн.
PPS: 100 гигабайт в куче?!! Ну, это виртуальная куча на кластере Hadoop, и MergeSort будет реализовываться параллельно на нескольких машинах, разделяющих нагрузку...
Ответ 6
Я новичок здесь. Я изменил решение Rama Hoetzlein (спасибо за идеи). Моя сортировка слияния не использует последний цикл обратной копии. Плюс он возвращается к сортировке вставки. Я сравнивал это на своем ноутбуке, и это самый быстрый. Даже лучше, чем рекурсивная версия. Кстати, он находится в java и сортируется по убыванию в порядке возрастания. И, конечно, это итеративно. Его можно сделать многопоточным. Код стал сложным. Поэтому, если кто-то заинтересован, пожалуйста, посмотрите.
Код:
int num = input_array.length;
int left = 0;
int right;
int temp;
int LIMIT = 16;
if (num <= LIMIT)
{
// Single Insertion Sort
right = 1;
while(right < num)
{
temp = input_array[right];
while(( left > (-1) ) && ( input_array[left] > temp ))
{
input_array[left+1] = input_array[left--];
}
input_array[left+1] = temp;
left = right;
right++;
}
}
else
{
int i;
int j;
//Fragmented Insertion Sort
right = LIMIT;
while (right <= num)
{
i = left + 1;
j = left;
while (i < right)
{
temp = input_array[i];
while(( j >= left ) && ( input_array[j] > temp ))
{
input_array[j+1] = input_array[j--];
}
input_array[j+1] = temp;
j = i;
i++;
}
left = right;
right = right + LIMIT;
}
// Remainder Insertion Sort
i = left + 1;
j = left;
while(i < num)
{
temp = input_array[i];
while(( j >= left ) && ( input_array[j] > temp ))
{
input_array[j+1] = input_array[j--];
}
input_array[j+1] = temp;
j = i;
i++;
}
// Rama Hoetzlein method
int[] temp_array = new int[num];
int[] swap;
int k = LIMIT;
while (k < num)
{
left = 0;
i = k;// The mid point
right = k << 1;
while (i < num)
{
if (right > num)
{
right = num;
}
temp = left;
j = i;
while ((left < i) && (j < right))
{
if (input_array[left] <= input_array[j])
{
temp_array[temp++] = input_array[left++];
}
else
{
temp_array[temp++] = input_array[j++];
}
}
while (left < i)
{
temp_array[temp++] = input_array[left++];
}
while (j < right)
{
temp_array[temp++] = input_array[j++];
}
// Do not copy back the elements to input_array
left = right;
i = left + k;
right = i + k;
}
// Instead of copying back in previous loop, copy remaining elements to temp_array, then swap the array pointers
while (left < num)
{
temp_array[left] = input_array[left++];
}
swap = input_array;
input_array = temp_array;
temp_array = swap;
k <<= 1;
}
}
return input_array;
Ответ 7
На всякий случай кто-то все еще скрывается в этой теме... Я применил алгоритм сортировки нерекурсивного слияния Rama Hoetzlein выше для сортировки двойных связанных списков. Этот новый вид на месте, стабилен и позволяет избежать дорогостоящего перераспределения кода кода, который в других реализациях сортировки слияния смежных списков.
// MergeSort.cpp
// Angus Johnson 2017
// License: Public Domain
#include "io.h"
#include "time.h"
#include "stdlib.h"
struct Node {
int data;
Node *next;
Node *prev;
Node *jump;
};
inline void Move2Before1(Node *n1, Node *n2)
{
Node *prev, *next;
//extricate n2 from linked-list ...
prev = n2->prev;
next = n2->next;
prev->next = next; //nb: prev is always assigned
if (next) next->prev = prev;
//insert n2 back into list ...
prev = n1->prev;
if (prev) prev->next = n2;
n1->prev = n2;
n2->prev = prev;
n2->next = n1;
}
void MergeSort(Node *&nodes)
{
Node *first, *second, *base, *tmp, *prev_base;
if (!nodes || !nodes->next) return;
int mul = 1;
for (;;) {
first = nodes;
prev_base = NULL;
//sort each successive mul group of nodes ...
while (first) {
if (mul == 1) {
second = first->next;
if (!second) {
first->jump = NULL;
break;
}
first->jump = second->next;
}
else
{
second = first->jump;
if (!second) break;
first->jump = second->jump;
}
base = first;
int cnt1 = mul, cnt2 = mul;
//the following 'if' condition marginally improves performance
//in an unsorted list but very significantly improves
//performance when the list is mostly sorted ...
if (second->data < second->prev->data)
while (cnt1 && cnt2) {
if (second->data < first->data) {
if (first == base) {
if (prev_base) prev_base->jump = second;
base = second;
base->jump = first->jump;
if (first == nodes) nodes = second;
}
tmp = second->next;
Move2Before1(first, second);
second = tmp;
if (!second) { first = NULL; break; }
--cnt2;
}
else
{
first = first->next;
--cnt1;
}
} //while (cnt1 && cnt2)
first = base->jump;
prev_base = base;
} //while (first)
if (!nodes->jump) break;
else mul <<= 1;
} //for (;;)
}
void InsertNewNode(Node *&head, int data)
{
Node *tmp = new Node;
tmp->data = data;
tmp->next = NULL;
tmp->prev = NULL;
tmp->jump = NULL;
if (head) {
tmp->next = head;
head->prev = tmp;
head = tmp;
}
else head = tmp;
}
void ClearNodes(Node *head)
{
if (!head) return;
while (head) {
Node *tmp = head;
head = head->next;
delete tmp;
}
}
int main()
{
srand(time(NULL));
Node *nodes = NULL, *n;
const int len = 1000000; //1 million nodes
for (int i = 0; i < len; i++)
InsertNewNode(nodes, rand() >> 4);
clock_t t = clock();
MergeSort(nodes); //~1/2 sec for 1 mill. nodes on Pentium i7.
t = clock() - t;
printf("Sort time: %d msec\n\n", t * 1000 / CLOCKS_PER_SEC);
n = nodes;
while (n)
{
if (n->prev && n->data < n->prev->data) {
printf("oops! sorting broken\n");
break;
}
n = n->next;
}
ClearNodes(nodes);
printf("All done!\n\n");
getchar();
return 0;
}
Отредактировано 2017-10-27: Исправлена ошибка, влияющая на списки с нечетными номерами
Ответ 8
Я написал следующий фрагмент кода с нуля с довольно базовыми знаниями.
Это моя интерпретация того, как должна работать итеративная сортировка слиянием:
-
Сохраняйте массив пополам до тех пор, пока не наберется масса отдельных элементов;
-
Возьмите один массив элементов в пару и объедините их, пока не будет только один массив.
function mergeSort(array) {
let len = array.length
let list = [array]
while (true) {
// keep halving array until there a moltitude of single item arrays
for (let i = list.length - 1; i > -1; i--) {
list.push(...halve(...list.splice(i, 1)))
}
if (list[0].length < 2) {
break
}
}
// take single item arrays in pair and merge-sort them until there only one array
while (true) {
for (let i = list.length - 1; i > 0; i -= 2) {
list.push(merge(...list.splice(i-1, 2)))
}
if (list[0].length === len) {
return list[0]
}
}
return list
}
// halving happens here
function halve(array) {
let n = array.length
if (n < 2) {
return [array]
}
let left = array.slice(0, n/2|0)
let right = array.slice(n/2|0)
if (left.length > right.length) {
return [left, right]
}
return [right, left]
}
// merging happens here
function merge(left, right) {
let merged = [] // result array to return
let i = 0
let j = 0
while ( i < left.length && j < right.length ) {
// choose the smallest from the two
if ( left[i] <= right[j] ) {
merged.push( left[i] )
i++
} else {
merged.push( right[j] )
j++
}
}
// push all the left-over
while( left[i] ) {
merged.push( left[i] )
i++
}
while( right[j] ) {
merged.push( right[j] )
j++
}
return merged
}
console.log(mergeSort([3,2,6,9,3,7,4,5,8,1,1]))