Нерекурсивная сортировка слиянием

Может кто-нибудь объяснить на английском, как работает нерекурсивная сортировка слиянием?

Спасибо

13.10.2009 02:03:20
Хотя bobbymcr дает хороший ответ, также обратите внимание, что рекурсия и итерация формально эквивалентны. См. Stackoverflow.com/questions/159590/…
Adam Rosenfield 13.10.2009 02:15:28
Взгляните на stackoverflow.com/a/23695092/3315914
rpax 1.10.2016 15:15:42
8 ОТВЕТОВ
РЕШЕНИЕ

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

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

15
13.10.2009 02:14:39
Слияние может быть выполнено на месте, но обычно это «сложно».
bobbymcr 13.10.2009 02:30:46
Тот, что на Алгоритмиста, не выглядит сложным. Однако вы потеряете некоторую локальность, если вы сортируете набор данных, слишком большой, чтобы уместиться в памяти
John La Rooy 13.10.2009 02:38:27
Ах, вы говорите о слиянии, а не о слиянии снизу вверх
John La Rooy 13.10.2009 02:39:13
Я спрашиваю о нерекурсивной сортировке слиянием, которая снизу вверх не является рекурсивной сортировкой слиянием.
DarthVader 13.10.2009 03:06:02
Как делятся массивы нечетной длины? Кажется, самый последний элемент никогда не будет отсортирован.
Saskia 30.08.2016 03:35:18

Цитата из Алгоритмиста :

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

9
13.10.2009 02:13:49
Да, каждый вид сортировки слиянием - это n log (n).
bobbymcr 13.10.2009 02:20:52

Как рекурсивная, так и нерекурсивная сортировка слиянием имеют одинаковую сложность времени O (nlog (n)). Это связано с тем, что оба подхода используют стек одним или другим способом.

В нерекурсивном подходе пользователь / программист определяет и использует стек

В рекурсивном подходе стек используется системой для хранения адреса возврата функции, которая вызывается рекурсивно

4
11.01.2013 06:59:54
Поскольку сортировка слиянием всегда выполняет свои операции разделения и сортировки в одной и той же последовательности, независимо от начального порядка элементов в наборе данных, нет необходимости использовать стек для отслеживания следующей операции. Все, что нужно, - это размер известных для сортировки разделов ( part_sizeизначально 1) и индекс первого такого объединяемого раздела ( next_partизначально нулевой). Для каждого «шага», объединять разделы размера part_sizeначиная с next_partи next_part+part_size, а затем поднять next_partна part_size*2. Если это упадет с конца массива, ...
supercat 4.04.2013 21:55:35
... удвоить part_sizeи установить next_partна ноль. Нет необходимости в рекурсии.
supercat 4.04.2013 21:55:59

Нерекурсивная сортировка слиянием работает с учетом размеров окна 1,2,4,8,16..2 ^ n над входным массивом. Для каждого окна ('k' в приведенном ниже коде) все смежные пары окон объединяются во временное пространство, а затем помещаются обратно в массив.

Вот моя единственная функция, основанная на C, не рекурсивная сортировка слиянием. Вход и выход находятся в «а». Временное хранение в «б». Однажды я хотел бы иметь версию, которая была на месте:

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).

20
30.07.2013 20:56:26
я пробовал подобный подход здесь stackoverflow.com/questions/37366365/… но не могу понять, как обрабатывать входные размеры не в форме 2 ^ x, любая помощь?
Aishwat Singh 21.05.2016 18:43:24
Вы можете существенно упростить код, объединив некоторые строки, например, b[m++]=a[i++];для b[m]=a[i]; i++; m++;.
user3932000 2.05.2017 05:23:42
Не менее увлекательно, чем усложнять понимание, сжимая ваш код. Думаю, вы обнаружите, что большинство работодателей предпочли бы, чтобы код был более читабельным для человека, вместо того, чтобы демонстрировать, как много можно сделать в одной строке. Я бы порекомендовал переместить строки j ++ и m ++ в отдельные строки и, возможно, использовать некоторые комментарии, если не более значимые имена переменных. И используя постоянный пробел между вашими заданиями. Если вы не добавляете конечные пробелы, всем нравится код, который легко на глаз. Дисковое пространство никогда не является проблемой, все компилируется одинаково. Запутанный код - это дьявол. : P
Raishin 30.12.2017 04:12:29
@Raishin большинство работодателей ищут умных программистов.
PHPst 18.08.2018 07:35:17

Основная причина, по которой вы хотите использовать нерекурсивную сортировку MergeSort, состоит в том, чтобы избежать переполнения стека рекурсии. Я, например, пытаюсь отсортировать 100 миллионов записей, каждая запись длиной около 1 кБайт (= 100 гигабайт), в алфавитно-цифровом порядке. Для сортировки по порядку (N ^ 2) потребуется 10 ^ 16 операций, т. Е. Потребуются десятилетия для запуска даже при 0,1 микросекунде на операцию сравнения. Сортировка слиянием порядка (N log (N)) займет менее 10 ^ 10 операций или менее часа, чтобы работать с той же рабочей скоростью. Однако в рекурсивной версии MergeSort сортировка 100 миллионов элементов приводит к 50 миллионам рекурсивных вызовов MergeSort (). При рекурсии стека в несколько сотен байтов это переполняет стек рекурсии, даже если процесс легко помещается в динамическую память. Выполнение сортировки слиянием с использованием динамически выделяемой памяти в куче. Я использую код, предоставленный Рамой Хетцляйном выше, но я использую динамически распределенную память в куче вместо использования стека. Я могу отсортировать свои 100 миллионов записей с помощью нерекурсивная сортировка слиянием, и я не переполняю стек. Соответствующий разговор для сайта "Stack Overflow"!

PS: спасибо за код, Рама Хетцляйн.

PPS: 100 гигабайт в куче? !! Ну, это виртуальная куча в кластере Hadoop, и MergeSort будет реализован параллельно на нескольких машинах, распределяющих нагрузку ...

4
4.09.2014 23:40:17

Я новенький здесь. Я модифицировал раствор Рамы Хетцляйн (спасибо за идеи). Моя сортировка слиянием не использует последний цикл обратной копии. Плюс это возвращается к сортировке вставки. Я проверил его на своем ноутбуке, и он самый быстрый. Даже лучше, чем рекурсивная версия. Кстати, это в 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;
1
21.02.2017 20:31:05

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

// 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's broken\n"); 
            break;
        }
        n = n->next;
    }
    ClearNodes(nodes);
    printf("All done!\n\n");
    getchar();
    return 0;
}

Отредактировано 2017-10-27: исправлена ​​ошибка, затрагивающая нечетные списки

0
27.10.2017 08:59:55

Интерес к этому больше? Возможно нет. Ну что ж. Тут ничего не происходит.

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

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

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

0
14.03.2020 05:44:21