J'ai ci-dessous le programme de tri de la fusion dans le livre d'algorithmes, il est mentionné que le problème principal est que la fusion de deux listes triées nécessite une mémoire supplémentaire linéaire et que les travaux supplémentaires passés à la copie au tableau temporaire et à l'arrière de l'algorithme, ont le effet de ralentir considérablement le genre. Cette copie peut être évitée en commutant judicieusement les rôles de "A" et "Tmp_array" à des niveaux alternatifs de la récursion.
Ma question est ce que l'auteur signifie que "la copie peut être évitée de manière judicieuse commutant les rôles d'A et TMP_Array à Des niveaux alternatifs de la récursion »et comment il est possible dans le code suivant? Demande de montrer un exemple comment nous pouvons y parvenir? P>
void mergesort( input_type a[], unsigned int n ) {
input_type *tmp_array;
tmp_array = (input_type *) malloc( (n+1) * sizeof (input_type) );
m_sort( a, tmp_array, 1, n );
free( tmp_array );
}
void m_sort( input_type a[], input_type tmp_array[ ], int left, int right ) {
int center;
if( left < right ) {
center = (left + right) / 2;
m_sort( a, tmp_array, left, center );
m_sort( a, tmp_array, center+1, right );
merge( a, tmp_array, left, center+1, right );
}
}
void merge( input_type a[ ], input_type tmp_array[ ], int l_pos, int r_pos, int right_end ) {
int i, left_end, num_elements, tmp_pos;
left_end = r_pos - 1;
tmp_pos = l_pos;
num_elements = right_end - l_pos + 1;
/* main loop */
while( ( 1_pos <= left_end ) && ( r_pos <= right_end ) )
if( a[1_pos] <= a[r_pos] )
tmp_array[tmp_pos++] = a[l_pos++];
else
tmp_array[tmp_pos++] = a[r_pos++];
while( l_pos <= left_end ) /* copy rest of first half */
tmp_array[tmp_pos++] = a[l_pos++];
while( r_pos <= right_end ) /* copy rest of second half */
tmp_array[tmp_pos++] = a[r_pos++];
/* copy tmp_array back */
for(i=1; i <= num_elements; i++, right_end-- )
a[right_end] = tmp_array[right_end];
}
4 Réponses :
Commencez par penser à la fusion de la sorte de cette manière.
0: Considérons le tableau d'entrée A0 comme collection de séquences commandées de Longueur 1.
1: fusionner chaque paire de séquences consécutives de A0, construisant un Nouveau tableau temporaire A1.
2: fusionner chaque paire de séquences consécutives de A1, construisant un Nouveau tableau temporaire A2.
...
Terminer lorsque la dernière itération entraîne une seule séquence.
Maintenant, vous pouvez évidemment s'en tirer avec juste un seul tableau temporaire en faisant ceci:
0: Considérons le tableau d'entrée A0 comme collection de séquences commandées de Longueur 1.
1: fusionner chaque paire de séquences consécutives de A0, construisant un Nouveau tableau temporaire A1.
2: fusionner chaque paire de séquences consécutives de A1, écrasement A0 avec le résultat.
3: fusionner chaque paire de séquences consécutives de A0, écrasement A1 avec le résultat.
...
Terminer lorsque la dernière itération entraîne une seule séquence.
Bien sûr, vous pouvez être encore plus intelligent que cela. Si vous souhaitez être plus agréable au cache, vous pouvez décider de trier de haut en bas, plutôt que de bas en haut. Dans ce cas, j'espère devenir évident ce que votre manuel signifie lorsqu'il s'agit de suivre le rôle des tableaux à différents niveaux de récursion.
J'espère que cela aide.
Regardez la dernière partie de la fonction de fusion. Et si, au lieu de copier ces données, vous avez simplement utilisé les connaissances que la partie triée est maintenant dans Les détails sont laissés comme un exercice pour le lecteur. tmp_array au lieu de A lorsque la fonction renvoie et a < / code> est disponible pour une utilisation en tant que temp.
.
Je vais supposer que, sans regarder ce code, il effectue le tri par fusion en déclarant un bloc contigu de mémoire de la même taille que l'original
Donc, normalement, sorte de fusion est comme ceci: p >
Je suppose que c'est récursive, donc pas de copies sera fait avant nous le tri sous-réseaux de taille 2. Maintenant, ce qui se passe? P>
( 4 6 7 8 10)(1 2 3 5 9 11)(... other sub-arrays) ( 1)(6 7 8 10)(4)(2 3 5 9 11)(... ( 1 2)(7 8 10)(4 6)(3 5 9 11) ... ( 1 2 3)(8 10)(4 6 7)(5 9 11) ( 1 2 3 4(10)(8)(6 7)(5 9 11) ooph :-( ( 1 2 3 4 5)(8)(6 7)(10)(9 11) ooph
Voici ma mise en œuvre sans copies supplémentaires.
public static void sort(ArrayList<Integer> input) {
mergeSort(input, 0, input.size() - 1);
}
/**
* Sorts input and returns inversions number
* using classical divide and conquer approach
*
* @param input Input array
* @param start Start index
* @param end End index
* @return int
*/
private static long mergeSort(ArrayList<Integer> input, int start, int end) {
if (end - start < 1) {
return 0;
}
long inversionsNumber = 0;
// 1. divide input into subtasks
int pivot = start + (int) Math.ceil((end - start) / 2);
if (end - start > 1) {
inversionsNumber += mergeSort(input, start, pivot);
inversionsNumber += mergeSort(input, pivot + 1, end);
}
// 2. Merge the results
int offset = 0;
int leftIndex = start;
int rightIndex = pivot + 1;
while (leftIndex <= pivot && rightIndex <= end) {
if (input.get(leftIndex + offset) <= input.get(rightIndex)) {
if (leftIndex < pivot) {
leftIndex++;
} else {
rightIndex++;
}
continue;
}
moveElement(input, rightIndex, leftIndex + offset);
inversionsNumber += rightIndex - leftIndex - offset;
rightIndex++;
offset++;
}
return inversionsNumber;
}
private static void moveElement(ArrayList<Integer> input, int from, int to) {
assert 0 <= to;
assert to < from;
assert from < input.size();
int temp = input.get(from);
for (int i = from; i > to; i--) {
input.set(i, input.get(i - 1));
}
input.set(to, temp);
}