Tri De Fusion Non Récursif

Le tri de fusion Non récursif fonctionne en considérant la taille des fenêtres de 1,2,4,8,16..2^N sur le tableau d'entrée. Pour chaque fenêtre ('k' dans le code ci-dessous), toutes les paires de fenêtres adjacentes sont fusionnées dans un espace temporaire, puis replacées dans le tableau.

Voici ma fonction unique, basée sur C, tri de fusion non récursif. L'entrée et la sortie sont dans 'un'. Stockage temporaire en "b". Un jour, j'aimerais avoir une version qui était en place:

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]; 
            }
        }
    }
}

En passant, il est également très facile de prouver que C'est O (n log n). La taille de la boucle externe sur la fenêtre augmente en tant que puissance de deux, donc k a des itérations log n. Bien qu'il y ait beaucoup de fenêtres couvertes par la boucle interne, ensemble, toutes les fenêtres pour un K donné couvrent exactement le tableau d'entrée, donc la boucle interne est O (N). Combinaison de boucles internes et externes: O(n)*O(log n) = O(n log n).

Citation de Algorithmist :

Le tri de fusion Ascendant est un variante non récursive de la fusion trier, dans lequel le tableau est trié par une séquence de passes. Au cours de chaque passer, le tableau est divisé en blocs de taille m. (Initialement, m = 1). Tous les deux blocs adjacents sont fusionnés (comme dans le tri de fusion normal), et le le prochain passage est fait avec un deux fois plus grand la valeur de m.

Le tri de fusion récursif et non récursif a la même complexité temporelle de O (nlog (n)). C'est parce que les deux approches utilisent stack d'une manière ou d'une autre.

En approche non récursive l'utilisateur/programmeur définit et utilise la pile

Dans L'approche récursive, la pile est utilisée en interne par le système pour stocker l'adresse de retour de la fonction appelée récursivement

La principale raison pour laquelle vous souhaitez utiliser un MergeSort non récursif est d'éviter le débordement de pile de récursivité. J'essaie par exemple de trier 100 millions d'enregistrements, chaque enregistrement d'environ 1 Ko de longueur (= 100 gigaoctets), dans l'ordre alphanumérique. Un tri order(N^2) prendrait 10^16 opérations, c'est-à-dire qu'il faudrait des décennies pour fonctionner même à 0,1 microseconde par opération de comparaison. Un tri de fusion order (n log(n)) prendra moins de 10 ^ 10 opérations ou moins d'une heure pour s'exécuter à la même vitesse opérationnelle. Cependant, dans la version récursive de MergeSort, le tri de 100 millions d'éléments entraîne 50 millions d'appels récursifs à MergeSort( ). À quelques centaines d'octets par récursion de pile, cela déborde la pile de récursion même si le processus s'intègre facilement dans la mémoire de tas. Faire le tri de fusion en utilisant la mémoire allouée dynamiquement sur le tas - j'utilise le code fourni par Rama Hoetzlein ci-dessus, mais j'utilise la mémoire allouée dynamiquement sur le tas au lieu d'utiliser la pile-je peux trier mon 100 millions d'enregistrements avec le tri de fusion non récursif et je ne déborde pas la pile. Une conversation appropriée pour le site Web "Stack Overflow"!

PS: merci pour le code, Rama Hoetzlein.

PPS: 100 gigaoctets sur le tas?!! Eh bien, c'est un tas virtuel sur un cluster Hadoop, et le MergeSort sera implémenté en parallèle sur plusieurs machines partageant la charge...

Je suis nouveau ici. J'ai modifié la solution Rama Hoetzlein (merci pour les idées). Mon tri de fusion n'utilise pas la dernière boucle de copie arrière. De plus, il retombe sur le tri d'insertion. Je l'ai comparé sur mon ordinateur portable et c'est le plus rapide. Encore mieux que la version récursive. En passant, il est en java et trie de l'ordre décroissant à l'ordre croissant. Et bien sûr, il est itératif. Il peut être fait multithread. Le code est devenu complexe. Donc, si quelqu'un est intéressé, veuillez avoir un regarder.

Code:

    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;

Juste au cas où quelqu'un se cache encore dans ce fil... J'ai adapté l'algorithme de tri de fusion non récursif de Rama Hoetzlein ci-dessus pour trier les listes à double lien. Ce nouveau tri est en place, stable et évite le code de division de liste coûteux en temps qui se trouve dans d'autres implémentations de tri de fusion de liste liée.

// 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;
}

Édité 2017-10-27: correction d'un bug affectant les listes impaires