algorithm - recursive - mergesort c++ codigo
Tipo de fusión no recursiva (7)
Cita de un Algorithmist :
La ordenación de fusión ascendente es una variante no recursiva de la ordenación de combinación, en la que la matriz está ordenada por una secuencia de pases. Durante cada paso, la matriz se divide en bloques de tamaño m . (Inicialmente, m = 1 ). Cada dos bloques adyacentes se fusionan (como en la clasificación de fusión normal), y la siguiente pasada se realiza con un valor dos veces mayor de m .
¿Puede alguien explicar en inglés cómo funciona la ordenación de fusión no recursiva?
Gracias
En caso de que alguien siga al acecho en este hilo ... He adaptado el algoritmo de orden de fusión no recursivo de Rama Hoetzlein para ordenar las listas de enlaces dobles. Esta nueva clasificación es in situ, estable y evita el costoso código de división de listas que está en otras implementaciones de clasificación de combinación de listas vinculadas.
// 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;
}
Editado 2017-10-27: Se corrigió un error que afectaba a las listas de números impares
La ordenación de fusión no recursiva funciona al considerar tamaños de ventana de 1,2,4,8,16..2 ^ n sobre la matriz de entrada. Para cada ventana (''k'' en el código a continuación), todos los pares de ventanas adyacentes se combinan en un espacio temporal y luego se colocan de nuevo en la matriz.
Aquí está mi función única, basada en C, ordenación de fusión no recursiva. La entrada y la salida están en ''a''. Almacenamiento temporal en ''b''. Un día, me gustaría tener una versión que estaba en el lugar:
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];
}
}
}
}
Por cierto, también es muy fácil probar que esto es O (n log n). El bucle exterior sobre el tamaño de la ventana crece como potencia de dos, por lo que k tiene log n iteraciones. Si bien hay muchas ventanas cubiertas por un bucle interno, todas las ventanas para un k dado cubren exactamente la matriz de entrada, por lo que el bucle interno es O (n). Combinación de bucles internos y externos: O (n) * O (log n) = O (n log n).
La razón principal por la que querría usar un MergeSort no recursivo es para evitar el desbordamiento de la pila de recursión. Por ejemplo, estoy tratando de ordenar 100 millones de registros, cada uno de los cuales mide aproximadamente 1 kByte de longitud (= 100 gigabytes), en orden alfanumérico. Una ordenación (N ^ 2) tomaría 10 ^ 16 operaciones, es decir, llevaría décadas ejecutarse incluso a 0,1 microsegundo por operación de comparación. Una orden (N log (N)) Merge Sort llevará menos de 10 ^ 10 operaciones o menos de una hora para ejecutarse a la misma velocidad operativa. Sin embargo, en la versión recursiva de MergeSort, la ordenación de 100 millones de elementos da como resultado 50 millones de llamadas recursivas al MergeSort (). A unos pocos cientos de bytes por recursión de pila, esto desborda la pila de recursión aunque el proceso cabe fácilmente dentro de la memoria del montón. Haciendo la clasificación de fusión usando la memoria asignada dinámicamente en el montón-- Estoy usando el código proporcionado por Rama Hoetzlein arriba, pero estoy usando la memoria asignada dinámicamente en el montón en lugar de usar la pila - Puedo ordenar mis 100 millones de registros con el La orden de fusión no recursiva y no desbordo la pila. Una conversación apropiada para el sitio web ""!
PD: Gracias por el código, Rama Hoetzlein.
PPS: 100 gigabytes en el montón? Bueno, es un montón virtual en un clúster de Hadoop, y el MergeSort se implementará en paralelo en varias máquinas que comparten la carga ...
Recorra los elementos y ordene cada grupo adyacente de dos intercambiando los dos cuando sea necesario.
Ahora, al tratar con grupos de dos grupos (cualquiera de los dos, lo más probable es que los grupos adyacentes, pero podría usar el primer y el último grupo), fusionarlos en un grupo seleccionando el elemento con el valor más bajo de cada grupo repetidamente hasta que los 4 elementos se combinen en una grupo de 4. Ahora, no tiene nada más que grupos de 4 más un posible resto. Usando un bucle alrededor de la lógica anterior, vuelva a hacerlo todo excepto que esta vez trabaje en grupos de 4. Este bucle se ejecuta hasta que solo haya un grupo.
Soy nuevo aquí. He modificado la solución de Rama Hoetzlein (gracias por las ideas). Mi orden de fusión no utiliza el último bucle de copia de copia. Además recae en la ordenación por inserción. Lo he evaluado en mi computadora portátil y es el más rápido. Incluso mejor que la versión recursiva. Por cierto, está en java y se ordena de orden descendente a orden ascendente. Y por supuesto es iterativo. Se puede hacer multiproceso. El código se ha vuelto complejo. Así que si alguien interesado, por favor, eche un vistazo.
Código:
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;
Tanto la ordenación de fusión recursiva como la no recursiva tienen la misma complejidad de tiempo de O (nlog (n)). Esto se debe a que ambos enfoques utilizan la pila de una u otra manera.
En un enfoque no recursivo, el usuario / programador define y usa la pila
En la pila de aproximación recursiva, el sistema la utiliza internamente para almacenar la dirección de retorno de la función que se llama de forma recursiva