Non ricorsiva merge sort
https://stackoverflow.com/questions/1557894
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Qualcuno può spiegare in inglese come fa merge non ricorsiva sorta funziona?
Grazie
Soluzione
Loop attraverso gli elementi e rendere ogni gruppo adiacente di due filtrate scambiando i due quando necessario.
Ora, si tratta di gruppi di due gruppi (due qualsiasi, molto probabilmente gruppi adiacenti, ma è possibile utilizzare i primi e gli ultimi gruppi) fonderli in un unico gruppo da selezionare l'elemento del valore più basso di ogni gruppo più volte fino a quando tutti e 4 gli elementi sono fusi in un gruppo di 4. Ora, non hai niente, ma gruppi di 4, più un eventuale resto. Utilizzando un anello intorno alla logica precedente, fare tutto di nuovo, tranne questo lavoro volta in gruppi di 4. Questo ciclo viene eseguito finché non ci sarà un solo gruppo.
Altri suggerimenti
non ricorsivo merge sort funziona considerando le dimensioni della finestra di 1,2,4,8,16..2 ^ n sopra la matrice di ingresso. Per ogni finestra ( 'k' nel codice di seguito), tutte le coppie adiacenti di finestre sono fusi in uno spazio temporaneo, poi rimesso nella matrice.
Ecco la mia singola funzione, C-based, non ricorsivo merge sort. Ingresso e uscita sono in 'a'. Il deposito temporaneo in 'b'. Un giorno, mi piacerebbe avere una versione che era sul posto:
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];
}
}
}
}
Tra l'altro, è anche molto facile da dimostrare questo è O (n log n). L'anello esterno oltre la dimensione della finestra cresce come potenza di due, così k ha log n iterazioni. Mentre ci sono molte finestre coperte dal circuito interno, insieme, tutte le finestre per un dato k esattamente coprono l'array di input, ciclo in modo interno è O (n). La combinazione di cicli interni ed esterni:. O (n) * O (log n) = O (n log n)
Bottom-up merge sort è un variante non ricorsiva della fusione ordinamento, in cui l'array è ordinato per una sequenza di passaggi. Nel corso di ogni passare, la matrice è divisa in blocchi di dimensioni m . (Inizialmente, m = 1 ). Ogni due blocchi adiacenti vengono fuse (Come nel normale merge sort), e la passo successivo è realizzato con un doppio grande valore di m .
Sia ricorsiva e non ricorsiva merge sort avere stesso tempo la complessità di O (nlog (n)). Questo perché entrambi gli approcci utilizzano stack uno o l'altro modo.
Nel approccio non ricorsivo l'utente / programmatore definisce e utilizza pila
In pila approccio ricorsivo viene utilizzato internamente dal sistema per memorizzare l'indirizzo di ritorno della funzione che viene chiamata ricorsivamente
Il motivo principale che si desidera utilizzare un MergeSort non ricorsiva è quello di evitare la ricorsione overflow dello stack. Io per esempio sto cercando di ordinare 100 milioni di dischi, ogni record di circa 1 kbyte di lunghezza (= 100 gigabyte), in ordine alfanumerico. Un ordine (N ^ 2) ordina avrebbe 10 ^ 16 operazioni, cioè ci vorrebbero decenni per funzionare anche a 0,1 microsecondi per confrontare funzionamento. Un ordine (log N (N)) merge sort avrà meno di 10 ^ 10 operazioni o meno di un'ora a funzionare alla stessa velocità operativa. Tuttavia, nella versione ricorsiva del Mergesort l'elemento di 100 milioni di risultati Scelto in 50 milioni di chiamate ricorsive al MergeSort (). A poche centinaia di byte per pila ricorsione, questo trabocca lo stack ricorsione anche se il processo rientri memoria mucchio. Facendo il merge sort utilizzando memoria allocata dinamicamente sul heap-- Sto usando il codice fornito da Rama Hoetzlein sopra, ma io sto usando memoria allocata dinamicamente sul mucchio invece di utilizzare lo stack-- posso ordinare i miei 100 milioni di dischi con il non ricorsiva merge sort e non overflow dello stack. Una conversazione appropriata per il sito web "Stack Overflow"!
PS:. Grazie per il codice, Rama Hoetzlein
PPS:? 100 gigabyte sul mucchio !! Beh, si tratta di un mucchio virtuale su un cluster Hadoop, e il MergeSort sarà attuato in parallelo su più macchine la condivisione del carico ...
Sono nuovo qui. Ho modificato soluzione Rama Hoetzlein (grazie per le idee). Il mio merge sort non usa il loop back dell'ultima copia. Più esso ricade sul inserzione. Ho benchmark sul mio portatile ed è il più veloce. Ancora meglio rispetto alla versione ricorsiva. Tra l'altro è in Java e ordina da ordine decrescente di ordine crescente. E, naturalmente, è iterativo. Può essere fatto con multithreading. Il codice è diventato complesso. Quindi, se qualcuno interessati, si prega di dare un'occhiata.
Codice:
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;
Nel caso in cui nessuno è ancora in agguato in questa discussione ... Ho adattato algoritmo di ordinamento merge non ricorsiva di Rama Hoetzlein sopra per ordinare gli elenchi doppia collegate. Questo nuovo tipo è sul posto, stabile ed evita il tempo lista costoso dividendo codice che è in altre implementazioni lista collegata merge ordinamento.
// 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;
}
A cura 2017/10/27: Corretto un bug che colpisce liste dispari
