tipos sustancias soluciones separacion puras mezclas metodos las heterogeneas elementos ejemplos compuestos como clasifican arrays algorithm sorting mergesort in-place

arrays - sustancias - ¿Cómo ordenar in situ utilizando el algoritmo de clasificación de mezcla?



tipos de mezclas (9)

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

Todo lo que quiero es que alguien me diga cómo convertir una ordenación de fusión normal en una ordenación de fusión en el lugar (o una ordenación de fusión con una sobrecarga de espacio adicional constante).

Todo lo que puedo encontrar (en la red) son las páginas que dicen "es demasiado complejo" o "fuera del alcance de este texto".

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

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

Un ejemplo de bufferless mergesort 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 (@p b) if not found. */ { int i; for ( i = b-a; 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 (@p b) if not found. */ { int i; for ( i = b-a; 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, n-h); ip_merge_(v, v+h, v+n); } }

Un ejemplo de mergesort adaptativo (optimizado).

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

#include <stdlib.h> #include <string.h> 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); }

Acabo de probar el algoritmo de combinación en su lugar para la clasificación de combinación en JAVA mediante el uso del algoritmo de clasificación por inserción, siguiendo los siguientes pasos.
1) Dos matrices ordenadas están disponibles.
2) Compara los primeros valores de cada matriz; y coloca el valor más pequeño en la primera matriz.
3) Coloque el valor más grande en la segunda matriz mediante la ordenación por inserción (transversal de izquierda a derecha).
4) Luego, nuevamente compare el segundo valor de la primera matriz y el primer valor de la segunda matriz, y haga lo mismo. Pero cuando se produce el intercambio, hay alguna pista sobre cómo omitir la comparación de los elementos adicionales, pero solo se requiere el intercambio.

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

p.ej)

First___Array: 3, 7, 8, 9

Segunda matriz: 1, 2, 4, 5

Luego, 7, 8, 9 hace que la segunda matriz intercambie (mueva a la izquierda por uno) todos sus elementos por uno cada vez para ubicarse en el último.

Entonces, la suposición de que aquí se intercambian 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; } }

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

Mirando un paso de la fusión:

[... lista ordenada ... | x ... lista- A ... | y ... lista- B ...]

Sabemos que la secuencia ordenada es menor que 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 de que x sea ​​menor o igual que y , simplemente mueva el puntero al inicio de A en uno. En el caso de que y sea ​​menor que x , debe ordenarse aleatoriamente y más allá de la totalidad de A. Ese último paso es lo que hace que esto sea caro (excepto en casos degenerados).

Por lo general, es más barato (especialmente cuando las matrices solo contienen palabras individuales por elemento, por ejemplo, un puntero a una cadena o estructura) para intercambiar espacio por tiempo y tener una matriz temporal separada que se clasifica de un lado a otro.

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 la ordenación de fusión en el lugar utilizando la técnica original de Kronrod pero con una implementación más simple. Un ejemplo ilustrativo que ilustra esta técnica se puede encontrar aquí: http://www.logiccoder.com/TheSortProblem/BestMergeInfo.htm .

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

Incluyendo su "gran resultado", este documento describe un par de variantes de ordenación de fusión en el lugar (PDF):

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

Clasificación in situ con menos movimientos.

Jyrki Katajainen, Tomi A. Pasanen

Se muestra que una matriz de n elementos puede ordenarse utilizando O (1) espacio adicional, O (n log n / log log n) se mueve, 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 comparaciones con 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 por ahí, transmitida por un colega, pero no la he leído. Parece abarcar 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 óptima estable

Antonios symvonis

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

Knuth dejó esto como un ejercicio (Vol. 3, 5.2.5). Existe una ordenación de fusión en el lugar. Debe ser implementado con cuidado.

Primero, la combinación ingenua en el lugar como se describe here no es la solución correcta. Baja la performance a O (N 2 ) .

La idea es ordenar parte de la matriz mientras se usa el resto como área de trabajo para la fusión.

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 sub matrices 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 array ordenado y el área de trabajo. Como resultado, el área de trabajo anterior contiene los elementos ordenados combinados, mientras que los elementos anteriores almacenados en el área de trabajo se mueven a los dos arreglos secundarios.

Sin embargo, hay dos restricciones que deben cumplirse:

  1. El área de trabajo debe estar dentro del límite de la matriz. En otras palabras, debe ser lo suficientemente grande como para mantener los 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, debe asegurarse de que no se sobrescriban elementos no combinados;

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

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

Una idea intuitiva es ordenar de forma recursiva otra mitad del área de trabajo, por lo tanto, solo hay 1/4 de elementos que aún no se han ordenado.

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

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

¿Queda el área de trabajo, que solo contiene 1/4 de elementos, lo suficientemente grande para fusionar A y B? Desafortunadamente, no lo es.

Sin embargo, la segunda restricción mencionada anteriormente nos da una pista de que podemos explotarla organizando el área de trabajo para que se superponga con cualquiera de los sub arreglos si podemos asegurar la secuencia de fusión de que los elementos no combinados no se sobrescribirán.

En realidad, en lugar de clasificar la segunda mitad del área de trabajo, podemos clasificar la primera mitad y colocar 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 matriz secundaria A. Esta idea se propone en [Jyrki Katajainen, Tomi Pasanen, Jukka Teuhola. `` Práctica combinación en el lugar ''''. Revista nórdica de computación, 1996].

Así que 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 clasificació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 se define wmerge anteriormente.

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

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

Realmente no es fácil ni eficiente, y te sugiero que no lo hagas a menos que realmente tengas que hacerlo (y probablemente no tengas que hacerlo a menos que esto sea tarea, ya que las aplicaciones de la fusión en el lugar son en su mayoría teóricas). ¿No puedes usar Quicksort en su lugar? Quicksort será más rápido de todos modos con unas pocas 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é: one y two . No estoy familiarizado con el tipo de combinación in situ, pero parece que la idea básica es usar rotaciones para facilitar la combinación de dos matrices sin utilizar memoria adicional.

Tenga en cuenta que esto es más lento incluso que el clásico orden de fusión que no está en su lugar.