Come ordinare sul posto usando l’algoritmo di merge sort?

So che la domanda non è troppo specifica.

Tutto quello che voglio è qualcuno che mi dica come convertire un ordinamento di tipo normale in un ordinamento di fusione diretto (o un ordinamento di tipo merge con overhead di spazio aggiuntivo costante).

Tutto quello che posso trovare (in rete) sono le pagine che dicono “è troppo complesso” o “fuori dallo scopo di questo testo”.

Gli unici metodi conosciuti per unire sul posto (senza spazio aggiuntivo) sono troppo complessi per essere ridotti al programma pratico. (preso da qui )

Anche se è troppo complesso, qual è il concetto di base su come rendere l’unificazione ordinata sul posto?

    Knuth ha lasciato questo come esercizio (Vol. 3, 5.2.5). Esiste un ordinamento di fusione diretto. Deve essere implementato attentamente.

    In primo luogo, l’inglobamento sul posto ingenuo come descritto qui non è la soluzione giusta. Riduce la prestazione a O (N 2 ) .

    L’idea è di ordinare una parte dell’array mentre si utilizza il resto come area di lavoro per l’unione.

    Ad esempio come la seguente funzione di unione.

    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++); } 

    Prende l'array xs , i due sotto array ordinati sono rappresentati rispettivamente come range [i, m) e [j, n) . L'area di lavoro inizia da w . Confrontato con l'algoritmo di fusione standard fornito nella maggior parte dei libri di testo, questo scambia il contenuto tra il sub-array ordinato e l'area di lavoro. Come risultato, l'area di lavoro precedente contiene gli elementi ordinati uniti, mentre gli elementi precedenti memorizzati nell'area di lavoro vengono spostati nei due sottoarray.

    Tuttavia, ci sono due vincoli che devono essere soddisfatti:

    1. L'area di lavoro dovrebbe essere all'interno del limite dell'array. In altre parole, dovrebbe essere abbastanza grande da contenere elementi scambiati senza causare errori fuori limite;
    2. L'area di lavoro può essere sovrapposta a uno dei due array ordinati, tuttavia, è necessario assicurarsi che non vengano sovrascritti elementi non separati;

    Con questo algoritmo di fusione definito, è facile immaginare una soluzione, che può ordinare metà dell'array; La prossima domanda è, come trattare con il resto della parte unsort memorizzata nell'area di lavoro come mostrato di seguito:

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

    Un'idea intuitiva è di ricorsivamente ordinare un'altra metà dell'area di lavoro, quindi ci sono solo 1/4 di elementi non ancora ordinati.

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

    Il punto chiave in questa fase è che dobbiamo unire i 1/4 elementi ordinati B con gli elementi 1/2 ordinati A prima o poi.

    È rimasta l'area di lavoro, che contiene solo 1/4 elementi, abbastanza grande da fondere A e B? Sfortunatamente, non lo è.

    Tuttavia, il secondo vincolo sopra menzionato ci dà un indizio, che possiamo sfruttarlo disponendo l'area di lavoro in modo che si sovrappongano con entrambi gli array secondari se possiamo garantire la sequenza di fusione che gli elementi non separati non verranno sovrascritti.

    In realtà, invece di ordinare la seconda metà dell'area di lavoro, possiamo ordinare la prima metà e mettere l'area di lavoro tra i due array ordinati in questo modo:

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

    Questi effetti di impostazione organizzano l'area di lavoro sovrapposta al sotto array A. Questa idea è proposta in [Jyrki Katajainen, Tomi Pasanen, Jukka Teuhola. "Missione pratica sul posto". Nordic Journal of Computing, 1996].

    Quindi, l'unica cosa rimasta è ripetere il passaggio precedente, che riduce l'area di lavoro da 1/2, 1/4, 1/8 ..., Quando l'area di lavoro diventa abbastanza piccola, ad esempio, rimangono solo due elementi, possiamo passare a un ordinamento di inserimento banale per terminare questo algoritmo.

    Ecco l'implementazione in ANSI C basata su questo 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); } } 

    Dove wmerge è definito in precedenza.

    Il codice sorgente completo può essere trovato qui e la spiegazione dettagliata può essere trovata qui

    A proposito, questa versione non è l'ordinamento di unione più veloce perché richiede più operazioni di scambio. Secondo il mio test, è più veloce della versione standard, che alloca spazi extra in ogni ricorsione. Ma è più lento della versione ottimizzata, che raddoppia la matrice originale in anticipo e la utilizza per ulteriori fusioni.

    Includendo il suo “grande risultato”, questo documento descrive un paio di varianti di unugge in-place sort (PDF):

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

    Ordinamento sul posto con meno mosse

    Jyrki Katajainen, Tomi A. Pasanen

    Viene mostrato che una matrice di n elementi può essere ordinata usando O (1) spazio extra, O (n log n / log log n) sposta elementi e n log 2 n + O (n log log n) confronti. Questo è il primo algoritmo di ordinamento sul posto che richiede o (n log n) spostamenti nel caso peggiore pur garantendo confronti O (n log n), ma a causa dei fattori costanti coinvolti l’algoritmo è prevalentemente di interesse teorico.

    Penso che anche questo sia rilevante. Ne ho uno stampato in giro, trasmesso da un collega, ma non l’ho letto. Sembra coprire la teoria di base, ma non ho familiarità con l’argomento per giudicare in modo completo:

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

    Ottimizzazione stabile ottimale

    Antonios Symvonis

    Questo documento mostra come unire stabilmente due sequenze A e B di dimensioni m e n, m ≤ n, rispettivamente, con O (m + n) assegnazioni, O (mlog (n / m + 1)) confronti e usando solo una costante quantità di spazio aggiuntivo. Questo risultato corrisponde a tutti i limiti inferiori conosciuti …

    Non è davvero facile o efficiente, e ti suggerisco di non farlo a meno che tu non sia realmente necessario (e probabilmente non devi farlo a meno che non si tratti di compiti a casa dato che le applicazioni di integrazione sul posto sono per lo più teoriche). Non puoi usare quicksort invece? Quicksort sarà comunque più veloce con alcune ottimizzazioni più semplici e la sua memoria extra è O (log N) .

    Ad ogni modo, se devi farlo, allora devi. Ecco cosa ho trovato: uno e due . Non ho familiarità con l’ordinamento di unplace inplace, ma sembra che l’idea di base sia quella di utilizzare le rotazioni per facilitare l’unione di due array senza utilizzare memoria extra.

    Si noti che questo è più lento persino rispetto al classico tipo merge che non è in posto.

    Il passaggio fondamentale consiste nel far sì che l’ unione stessa sia sul posto. Non è così difficile come fanno quelle fonti, ma perdi qualcosa quando provi.

    Guardando ad un passo dell’unione:

    [… elenco- ordinato … | x … list- A … | y … list- B …]

    Sappiamo che la sequenza ordinata è inferiore a tutto il resto, che x è inferiore a tutto il resto in A , e che y è inferiore a qualsiasi altra cosa in B. Nel caso in cui x sia minore o uguale a y , basta spostare il puntatore all’inizio di A su uno. Nel caso in cui y sia minore di x , devi mischiare y oltre l’intero A per essere ordinato . L’ultimo passaggio è ciò che rende questo costoso (tranne nei casi degenerati).

    Generalmente è più economico (specialmente quando gli array contengono solo parole singole per elemento, ad esempio un puntatore a una stringa o una struttura) per scambiare un po ‘di spazio per il tempo e disporre di un array temporaneo separato tra i due.

    Solo per riferimento, ecco una buona implementazione di un ordinamento di fusione stabile sul posto . Complicato, ma non troppo male.

    Ho finito per implementare sia un ordinamento di fusione stabile sul posto che un quicksort sul posto stabile in Java. Si noti che la complessità è O (n (log n) ^ 2)

    Un esempio di mergesort senza buffer in 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 esempio di adaptive mergesort (ottimizzato).

    Aggiunge codice di supporto e modifiche per accelerare l’unione quando è disponibile un buffer ausiliario di qualsiasi dimensione (funziona ancora senza memoria aggiuntiva). Utilizza fusione in avanti e all’indietro, rotazione anulare, fusione e ordinamento di piccole sequenze e 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); } 

    Questa è la mia versione 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--; } } } 

    Esiste un’implementazione relativamente semplice dell’ordinamento di merge sul posto usando la tecnica originale di Kronrod ma con un’implementazione più semplice. Un esempio pittorico che illustra questa tecnica può essere trovato qui: http://www.logiccoder.com/TheSortProblem/BestMergeInfo.htm .

    Ci sono anche link ad analisi teoriche più dettagliate dello stesso autore associato a questo link.

    Ho appena provato un algoritmo di fusione per l’unge sort in JAVA usando l’algoritmo di ordinamento per inserzione, usando i seguenti passi.
    1) Sono disponibili due array ordinati.
    2) Confrontare i primi valori di ciascun array; e posizionare il valore più piccolo nel primo array.
    3) Posiziona il valore più grande nel secondo array usando l’ordinamento per inserimento (attraversa da sinistra a destra).
    4) Quindi confrontare nuovamente il secondo valore del primo array e il primo valore del secondo array, e fare lo stesso. Ma quando accade lo scambio, c’è qualche indizio su saltare confrontando gli altri elementi, ma basta scambiare richiesto.

    Ho fatto qualche ottimizzazione qui; mantenere un minor numero di confronti nell’ordinamento per inserzione.
    L’unico svantaggio che ho trovato con queste soluzioni è che richiede uno swapping più ampio degli elementi dell’array nel secondo array.

    per esempio)

    First___Array: 3, 7, 8, 9

    Secondo array: 1, 2, 4, 5

    Quindi 7, 8, 9 fa in modo che il secondo array scambia (sposta a sinistra di uno) tutti i suoi elementi di uno ogni volta per posizionarsi nell’ultimo.

    Quindi l’ipotesi qui è lo scambio di articoli è trascurabile rispetto al confronto di due elementi.

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