¿Cómo ordenar en el lugar usando el algoritmo de ordenación por fusión?

Sé que la pregunta no es muy específica.

Todo lo que quiero es que alguien me diga cómo convertir un tipo de combinación normal en un tipo de fusión in situ (o un tipo de combinación con una sobrecarga de espacio adicional constante).

Todo lo que puedo encontrar (en la red) son páginas que dicen “es demasiado complejo” o “está fuera del scope de este texto”.

Las únicas formas conocidas de fusionarse en el lugar (sin ningún espacio adicional) son demasiado complejas para ser reducidas a un progtwig práctico. (tomado de aquí )

Incluso si es demasiado complejo, ¿cuál es el concepto básico de cómo ordenar la combinación en el lugar?

Knuth dejó esto como un ejercicio (Vol 3, 5.2.5). Existe el tipo de combinación in situ. Debe ser implementado cuidadosamente.

En primer lugar, la fusión ingenua en el lugar, tal como se describe aquí, no es la solución correcta. Reduce el rendimiento a O (N 2 ) .

La idea es ordenar parte de la matriz mientras usa el rest como área de trabajo para fusionar.

Por ejemplo, como la siguiente función de fusión.

void wmerge(Key* xs, int i, int m, int j, int n, int w) { while (i < m && j < n) swap(xs, w++, xs[i] < xs[j] ? i++ : j++); while (i < m) swap(xs, w++, i++); while (j < n) swap(xs, w++, j++); } 

Toma la matriz xs , las dos subcadenas ordenadas se representan como rango [i, m) y [j, n) respectivamente. El área de trabajo comienza desde w . Compare con el algoritmo de combinación estándar dado en la mayoría de los libros de texto, este intercambia los contenidos entre el sub conjunto ordenado y el área de trabajo. Como resultado, el área de trabajo anterior contiene los elementos ordenados fusionados, mientras que los elementos anteriores almacenados en el área de trabajo se mueven a los dos subordenadores.

Sin embargo, hay dos restricciones que se deben cumplir:

  1. El área de trabajo debe estar dentro del límite de la matriz. En otras palabras, debe ser lo suficientemente grande como para contener elementos intercambiados sin causar ningún error fuera de límite;
  2. El área de trabajo puede superponerse con cualquiera de las dos matrices ordenadas, sin embargo, se debe garantizar que no se sobreescriban elementos no fusionados;

Con este algoritmo de fusión definido, es fácil imaginar una solución, que puede ordenar la mitad de la matriz; La siguiente pregunta es cómo lidiar con el rest de la parte no ordenada almacenada en el área de trabajo como se muestra a continuación:

 ... unsorted 1/2 array ... | ... sorted 1/2 array ... 

Una idea intuitiva es recursiva ordenar otra mitad del área de trabajo, por lo tanto, solo hay 1/4 elementos no ordenados todavía.

 ... unsorted 1/4 array ... | sorted 1/4 array B | sorted 1/2 array A ... 

El punto clave en esta etapa es que debemos fusionar los elementos B 1/4 ordenados con los elementos 1/2 ordenados A tarde o temprano.

¿Está el área de trabajo a la izquierda, que solo tiene 1/4 elementos, lo suficientemente grande como para fusionar A y B? Lamentablemente, no lo es.

Sin embargo, la segunda restricción mencionada anteriormente nos da una pista, que podemos explotarlo organizando el área de trabajo para que se superponga con cualquier subarreglo si podemos asegurar que la secuencia de fusión no sobrescribirá los elementos no fusionados.

En realidad, en lugar de ordenar la segunda mitad del área de trabajo, podemos ordenar la primera mitad y ubicar el área de trabajo entre las dos matrices ordenadas de la siguiente manera:

 ... sorted 1/4 array B | unsorted work area | ... sorted 1/2 array A ... 

Estos efectos de configuración organizan la superposición del área de trabajo con la submatriz A. Esta idea se propone en [Jyrki Katajainen, Tomi Pasanen, Jukka Teuhola. `` Mergesort práctico en el lugar ''. Nordic Journal of Computing, 1996].

Entonces, lo único que queda es repetir el paso anterior, que reduce el área de trabajo de 1/2 ,, 1/4, 1/8 ..., cuando el área de trabajo se vuelve lo suficientemente pequeña, por ejemplo, solo quedan dos elementos, podemos cambiar a una ordenación de inserción trivial para finalizar este algoritmo.

Aquí está la implementación en ANSI C basada en este documento.

 void imsort(Key* xs, int l, int u); void swap(Key* xs, int i, int j) { Key tmp = xs[i]; xs[i] = xs[j]; xs[j] = tmp; } /* * sort xs[l, u), and put result to working area w. * constraint, len(w) == u - l */ void wsort(Key* xs, int l, int u, int w) { int m; if (u - l > 1) { m = l + (u - l) / 2; imsort(xs, l, m); imsort(xs, m, u); wmerge(xs, l, m, m, u, w); } else while (l < u) swap(xs, l++, w++); } void imsort(Key* xs, int l, int u) { int m, n, w; if (u - l > 1) { m = l + (u - l) / 2; w = l + u - m; wsort(xs, l, m, w); /* the last half contains sorted elements */ while (w - l > 2) { n = w; w = l + (n - l + 1) / 2; wsort(xs, w, n, l); /* the first half of the previous working area contains sorted elements */ wmerge(xs, l, l + n - w, n, u, w); } for (n = w; n > l; --n) /*switch to insertion sort*/ for (m = n; m < u && xs[m] < xs[m-1]; ++m) swap(xs, m, m - 1); } } 

Donde wmerge se define previamente.

El código fuente completo se puede encontrar aquí y la explicación detallada se puede encontrar aquí

Por cierto, esta versión no es la de fusión más rápida porque necesita más operaciones de intercambio. Según mi prueba, es más rápido que la versión estándar, que asigna espacios adicionales en cada recursión. Pero es más lento que la versión optimizada, que dobla la matriz original por adelantado y la usa para una mayor fusión.

Incluyendo su “gran resultado”, este documento describe un par de variantes de tipo de fusión in situ (PDF):

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.5514&rep=rep1&type=pdf

Clasificación en el lugar con menos movimientos

Jyrki Katajainen, Tomi A. Pasanen

Se muestra que una matriz de n elementos se puede ordenar usando O (1) espacio extra, movimientos de elementos O (n log n / log log n), y n log 2 n + O (n log log n) comparaciones. Este es el primer algoritmo de clasificación in situ que requiere o (n log n) movimientos en el peor de los casos al tiempo que garantiza las comparaciones O (n log n), pero debido a los factores constantes involucrados, el algoritmo es predominantemente de interés teórico.

Creo que esto también es relevante. Tengo una copia impresa de ella, me la pasó un colega, pero no la he leído. Parece cubrir la teoría básica, pero no estoy lo suficientemente familiarizado con el tema para juzgar de forma exhaustiva:

http://comjnl.oxfordjournals.org/cgi/content/abstract/38/8/681

Fusión estable óptima

Antonios Symvonis

Este artículo muestra cómo fusionar de manera estable dos secuencias A y B de tamaños m y n, m ≤ n, respectivamente, con asignaciones O (m + n), comparaciones O (mlog (n / m + 1)) y utilizando solo una constante cantidad de espacio adicional. Este resultado coincide con todos los límites inferiores conocidos …

Realmente no es fácil ni eficiente, y te sugiero que no lo hagas a menos que realmente tengas que hacerlo (y es probable que no tengas que hacerlo a menos que sea una tarea, ya que las aplicaciones de fusión in situ son principalmente teóricas). ¿No puedes usar quicksort en su lugar? Quicksort será más rápido de todos modos con algunas optimizaciones más simples y su memoria extra es O (log N) .

De todos modos, si debes hacerlo, entonces debes hacerlo. Esto es lo que encontré: uno y dos . No estoy familiarizado con el tipo de fusión in situ, pero parece que la idea básica es usar rotaciones para facilitar la fusión de dos matrices sin usar memoria extra.

Tenga en cuenta que esto es más lento incluso que el tipo de combinación clásica que no está en su lugar.

El paso crítico es conseguir que la fusión en sí misma esté en su lugar. No es tan difícil como hacen esas fonts, pero pierdes algo cuando lo intentas.

Mirando un paso de la fusión:

[… lista- ordenada … | x … list- A … | y … list- B …]

Sabemos que la secuencia ordenada es inferior a todo lo demás, que x es menor que todo lo demás en A , y que y es menor que todo lo demás en B. En el caso donde x es menor o igual a y , solo mueve su puntero al inicio de A en uno. En el caso en que y es menor que x , debes mezclar y pasar la totalidad de A para ordenarla . Ese último paso es lo que lo hace caro (excepto en casos degenerados).

En general es más económico (especialmente cuando las matrices solo contienen palabras sueltas por elemento, p. Ej., Un puntero a una cadena o estructura) para intercambiar espacio por tiempo y tener una matriz temporal separada por la que ordena de un lado a otro.

Solo como referencia, aquí hay una buena implementación de un tipo de fusión estable en el lugar . Complicado, pero no tan malo.

Terminé implementando una clasificación de fusión estable en el lugar y una conexión rápida estable en el lugar en Java. Tenga en cuenta que la complejidad es O (n (log n) ^ 2)

Un ejemplo de mergesort sin buffer en C.

 #define SWAP(type, a, b) \ do { type t=(a);(a)=(b);(b)=t; } while (0) static void reverse_(int* a, int* b) { for ( --b; a < b; a++, b-- ) SWAP(int, *a, *b); } static int* rotate_(int* a, int* b, int* c) /* swap the sequence [a,b) with [b,c). */ { if (a != b && b != c) { reverse_(a, b); reverse_(b, c); reverse_(a, c); } return a + (c - b); } static int* lower_bound_(int* a, int* b, const int key) /* find first element not less than @p key in sorted sequence or end of * sequence (@pb) if not found. */ { int i; for ( i = ba; i != 0; i /= 2 ) { int* mid = a + i/2; if (*mid < key) a = mid + 1, i--; } return a; } static int* upper_bound_(int* a, int* b, const int key) /* find first element greater than @p key in sorted sequence or end of * sequence (@pb) if not found. */ { int i; for ( i = ba; i != 0; i /= 2 ) { int* mid = a + i/2; if (*mid <= key) a = mid + 1, i--; } return a; } static void ip_merge_(int* a, int* b, int* c) /* inplace merge. */ { int n1 = b - a; int n2 = c - b; if (n1 == 0 || n2 == 0) return; if (n1 == 1 && n2 == 1) { if (*b < *a) SWAP(int, *a, *b); } else { int* p, * q; if (n1 <= n2) p = upper_bound_(a, b, *(q = b+n2/2)); else q = lower_bound_(b, c, *(p = a+n1/2)); b = rotate_(p, b, q); ip_merge_(a, p, b); ip_merge_(b, q, c); } } void mergesort(int* v, int n) { if (n > 1) { int h = n/2; mergesort(v, h); mergesort(v+h, nh); ip_merge_(v, v+h, v+n); } } 

Un ejemplo de mergesort adaptativo (optimizado).

Agrega código de soporte y modificaciones para acelerar la fusión cuando hay un búfer auxiliar de cualquier tamaño disponible (aún funciona sin memoria adicional). Utiliza fusión hacia adelante y hacia atrás, rotación de anillo, combinación y clasificación de secuencias pequeñas, y mergesort iterativo.

 #include  #include  static int* copy_(const int* a, const int* b, int* out) { int count = b - a; if (a != out) memcpy(out, a, count*sizeof(int)); return out + count; } static int* copy_backward_(const int* a, const int* b, int* out) { int count = b - a; if (b != out) memmove(out - count, a, count*sizeof(int)); return out - count; } static int* merge_(const int* a1, const int* b1, const int* a2, const int* b2, int* out) { while ( a1 != b1 && a2 != b2 ) *out++ = (*a1 <= *a2) ? *a1++ : *a2++; return copy_(a2, b2, copy_(a1, b1, out)); } static int* merge_backward_(const int* a1, const int* b1, const int* a2, const int* b2, int* out) { while ( a1 != b1 && a2 != b2 ) *--out = (*(b1-1) > *(b2-1)) ? *--b1 : *--b2; return copy_backward_(a1, b1, copy_backward_(a2, b2, out)); } static unsigned int gcd_(unsigned int m, unsigned int n) { while ( n != 0 ) { unsigned int t = m % n; m = n; n = t; } return m; } static void rotate_inner_(const int length, const int stride, int* first, int* last) { int* p, * next = first, x = *first; while ( 1 ) { p = next; if ((next += stride) >= last) next -= length; if (next == first) break; *p = *next; } *p = x; } static int* rotate_(int* a, int* b, int* c) /* swap the sequence [a,b) with [b,c). */ { if (a != b && b != c) { int n1 = c - a; int n2 = b - a; int* i = a; int* j = a + gcd_(n1, n2); for ( ; i != j; i++ ) rotate_inner_(n1, n2, i, c); } return a + (c - b); } static void ip_merge_small_(int* a, int* b, int* c) /* inplace merge. * @note faster for small sequences. */ { while ( a != b && b != c ) if (*a <= *b) a++; else { int* p = b+1; while ( p != c && *p < *a ) p++; rotate_(a, b, p); b = p; } } static void ip_merge_(int* a, int* b, int* c, int* t, const int ts) /* inplace merge. * @note works with or without additional memory. */ { int n1 = b - a; int n2 = c - b; if (n1 <= n2 && n1 <= ts) { merge_(t, copy_(a, b, t), b, c, a); } else if (n2 <= ts) { merge_backward_(a, b, t, copy_(b, c, t), c); } /* merge without buffer. */ else if (n1 + n2 < 48) { ip_merge_small_(a, b, c); } else { int* p, * q; if (n1 <= n2) p = upper_bound_(a, b, *(q = b+n2/2)); else q = lower_bound_(b, c, *(p = a+n1/2)); b = rotate_(p, b, q); ip_merge_(a, p, b, t, ts); ip_merge_(b, q, c, t, ts); } } static void ip_merge_chunk_(const int cs, int* a, int* b, int* t, const int ts) { int* p = a + cs*2; for ( ; p <= b; a = p, p += cs*2 ) ip_merge_(a, a+cs, p, t, ts); if (a+cs < b) ip_merge_(a, a+cs, b, t, ts); } static void smallsort_(int* a, int* b) /* insertion sort. * @note any stable sort with low setup cost will do. */ { int* p, * q; for ( p = a+1; p < b; p++ ) { int x = *p; for ( q = p; a < q && x < *(q-1); q-- ) *q = *(q-1); *q = x; } } static void smallsort_chunk_(const int cs, int* a, int* b) { int* p = a + cs; for ( ; p <= b; a = p, p += cs ) smallsort_(a, p); smallsort_(a, b); } static void mergesort_lower_(int* v, int n, int* t, const int ts) { int cs = 16; smallsort_chunk_(cs, v, v+n); for ( ; cs < n; cs *= 2 ) ip_merge_chunk_(cs, v, v+n, t, ts); } static void* get_buffer_(int size, int* final) { void* p = NULL; while ( size != 0 && (p = malloc(size)) == NULL ) size /= 2; *final = size; return p; } void mergesort(int* v, int n) { /* @note buffer size may be in the range [0,(n+1)/2]. */ int request = (n+1)/2 * sizeof(int); int actual; int* t = (int*) get_buffer_(request, &actual); /* @note allocation failure okay. */ int tsize = actual / sizeof(int); mergesort_lower_(v, n, t, tsize); free(t); } 

Esta es mi versión C:

 void mergesort(int *a, int len) { int temp, listsize, xsize; for (listsize = 1; listsize <= len; listsize*=2) { for (int i = 0, j = listsize; (j+listsize) <= len; i += (listsize*2), j += (listsize*2)) { merge(& a[i], listsize, listsize); } } listsize /= 2; xsize = len % listsize; if (xsize > 1) mergesort(& a[len-xsize], xsize); merge(a, listsize, xsize); } void merge(int *a, int sizei, int sizej) { int temp; int ii = 0; int ji = sizei; int flength = sizei+sizej; for (int f = 0; f < (flength-1); f++) { if (sizei == 0 || sizej == 0) break; if (a[ii] < a[ji]) { ii++; sizei--; } else { temp = a[ji]; for (int z = (ji-1); z >= ii; z--) a[z+1] = a[z]; ii++; a[f] = temp; ji++; sizej--; } } } 

Hay una implementación relativamente simple de ordenamiento de fusión in situ utilizando la técnica original de Kronrod pero con una implementación más simple. Puede encontrar un ejemplo ilustrativo que ilustra esta técnica aquí: http://www.logiccoder.com/TheSortProblem/BestMergeInfo.htm .

También hay enlaces a análisis teóricos más detallados del mismo autor asociado con este enlace.

Acabo de probar el algoritmo de fusión in situ para ordenar por fusión en JAVA utilizando el algoritmo de ordenación por inserción, usando los siguientes pasos.
1) Dos matrices ordenadas están disponibles.
2) Compare los primeros valores de cada matriz; y coloque el valor más pequeño en la primera matriz.
3) Coloque el valor más grande en la segunda matriz mediante la inserción de clasificación (transversal de izquierda a derecha).
4) Luego, vuelva a comparar el segundo valor de la primera matriz y el primer valor de la segunda matriz, y haga lo mismo. Pero cuando ocurre el intercambio, hay alguna pista al omitir la comparación de los elementos adicionales, pero solo se requiere el intercambio.

He hecho algo de optimización aquí; para mantener comparaciones menores en ordenación por inserción.
El único inconveniente que encontré con estas soluciones es que necesita un mayor intercambio de elementos de la matriz en la segunda matriz.

p.ej)

First___Array: 3, 7, 8, 9

Segunda matriz: 1, 2, 4, 5

Luego, 7, 8, 9 forman la segunda matriz para intercambiar (mover a la izquierda por uno) todos sus elementos por uno cada vez para colocarse en el último.

Por lo tanto, la suposición aquí es intercambiar elementos es insignificante en comparación con la comparación de dos elementos.

https://github.com/skanagavelu/algorithams/blob/master/src/sorting/MergeSort.java

 package sorting; import java.util.Arrays; public class MergeSort { public static void main(String[] args) { int[] array = { 5, 6, 10, 3, 9, 2, 12, 1, 8, 7 }; mergeSort(array, 0, array.length -1); System.out.println(Arrays.toString(array)); int[] array1 = {4, 7, 2}; System.out.println(Arrays.toString(array1)); mergeSort(array1, 0, array1.length -1); System.out.println(Arrays.toString(array1)); System.out.println("\n\n"); int[] array2 = {4, 7, 9}; System.out.println(Arrays.toString(array2)); mergeSort(array2, 0, array2.length -1); System.out.println(Arrays.toString(array2)); System.out.println("\n\n"); int[] array3 = {4, 7, 5}; System.out.println(Arrays.toString(array3)); mergeSort(array3, 0, array3.length -1); System.out.println(Arrays.toString(array3)); System.out.println("\n\n"); int[] array4 = {7, 4, 2}; System.out.println(Arrays.toString(array4)); mergeSort(array4, 0, array4.length -1); System.out.println(Arrays.toString(array4)); System.out.println("\n\n"); int[] array5 = {7, 4, 9}; System.out.println(Arrays.toString(array5)); mergeSort(array5, 0, array5.length -1); System.out.println(Arrays.toString(array5)); System.out.println("\n\n"); int[] array6 = {7, 4, 5}; System.out.println(Arrays.toString(array6)); mergeSort(array6, 0, array6.length -1); System.out.println(Arrays.toString(array6)); System.out.println("\n\n"); //Handling array of size two int[] array7 = {7, 4}; System.out.println(Arrays.toString(array7)); mergeSort(array7, 0, array7.length -1); System.out.println(Arrays.toString(array7)); System.out.println("\n\n"); int input1[] = {1}; int input2[] = {4,2}; int input3[] = {6,2,9}; int input4[] = {6,-1,10,4,11,14,19,12,18}; System.out.println(Arrays.toString(input1)); mergeSort(input1, 0, input1.length-1); System.out.println(Arrays.toString(input1)); System.out.println("\n\n"); System.out.println(Arrays.toString(input2)); mergeSort(input2, 0, input2.length-1); System.out.println(Arrays.toString(input2)); System.out.println("\n\n"); System.out.println(Arrays.toString(input3)); mergeSort(input3, 0, input3.length-1); System.out.println(Arrays.toString(input3)); System.out.println("\n\n"); System.out.println(Arrays.toString(input4)); mergeSort(input4, 0, input4.length-1); System.out.println(Arrays.toString(input4)); System.out.println("\n\n"); } private static void mergeSort(int[] array, int p, int r) { //Both below mid finding is fine. int mid = (r - p)/2 + p; int mid1 = (r + p)/2; if(mid != mid1) { System.out.println(" Mid is mismatching:" + mid + "/" + mid1+ " for p:"+p+" r:"+r); } if(p < r) { mergeSort(array, p, mid); mergeSort(array, mid+1, r); // merge(array, p, mid, r); inPlaceMerge(array, p, mid, r); } } //Regular merge private static void merge(int[] array, int p, int mid, int r) { int lengthOfLeftArray = mid - p + 1; // This is important to add +1. int lengthOfRightArray = r - mid; int[] left = new int[lengthOfLeftArray]; int[] right = new int[lengthOfRightArray]; for(int i = p, j = 0; i <= mid; ){ left[j++] = array[i++]; } for(int i = mid + 1, j = 0; i <= r; ){ right[j++] = array[i++]; } int i = 0, j = 0; for(; i < left.length && j < right.length; ) { if(left[i] < right[j]){ array[p++] = left[i++]; } else { array[p++] = right[j++]; } } while(j < right.length){ array[p++] = right[j++]; } while(i < left.length){ array[p++] = left[i++]; } } //InPlaceMerge no extra array private static void inPlaceMerge(int[] array, int p, int mid, int r) { int secondArrayStart = mid+1; int prevPlaced = mid+1; int q = mid+1; while(p < mid+1 && q <= r){ boolean swapped = false; if(array[p] > array[q]) { swap(array, p, q); swapped = true; } if(q != secondArrayStart && array[p] > array[secondArrayStart]) { swap(array, p, secondArrayStart); swapped = true; } //Check swapped value is in right place of second sorted array if(swapped && secondArrayStart+1 <= r && array[secondArrayStart+1] < array[secondArrayStart]) { prevPlaced = placeInOrder(array, secondArrayStart, prevPlaced); } p++; if(q < r) { //q+1 <= r) { q++; } } } private static int placeInOrder(int[] array, int secondArrayStart, int prevPlaced) { int i = secondArrayStart; for(; i < array.length; i++) { //Simply swap till the prevPlaced position if(secondArrayStart < prevPlaced) { swap(array, secondArrayStart, secondArrayStart+1); secondArrayStart++; continue; } if(array[i] < array[secondArrayStart]) { swap(array, i, secondArrayStart); secondArrayStart++; } else if(i != secondArrayStart && array[i] > array[secondArrayStart]){ break; } } return secondArrayStart; } private static void swap(int[] array, int m, int n){ int temp = array[m]; array[m] = array[n]; array[n] = temp; } }