Explication de la Fusion de Tri pour les Nuls

Quand je suis tombé dans la difficulté à uderstand fonctionnement de l'algorithme, - je ajouter de la sortie de débogage pour vérifier ce qui se passe réellement à l'intérieur de l'algorithme.

Voici le code avec la sortie de débogage. Essayez de uderstand toutes les étapes avec les appels récursifs de mergesort et ce merge ne avec le de sortie:

def merge(left, right):
result = []
i ,j = 0, 0
while i < len(left) and j < len(right):
print('left[i]: {} right[j]: {}'.format(left[i],right[j]))
if left[i] <= right[j]:
print('Appending {} to the result'.format(left[i]))           
result.append(left[i])
print('result now is {}'.format(result))
i += 1
print('i now is {}'.format(i))
else:
print('Appending {} to the result'.format(right[j]))
result.append(right[j])
print('result now is {}'.format(result))
j += 1
print('j now is {}'.format(j))
print('One of the list is exhausted. Adding the rest of one of the lists.')
result += left[i:]
result += right[j:]
print('result now is {}'.format(result))
return result
def mergesort(L):
print('---')
print('mergesort on {}'.format(L))
if len(L) < 2:
print('length is 1: returning the list withouth changing')
return L
middle = len(L) / 2
print('calling mergesort on {}'.format(L[:middle]))
left = mergesort(L[:middle])
print('calling mergesort on {}'.format(L[middle:]))
right = mergesort(L[middle:])
print('Merging left: {} and right: {}'.format(left,right))
out = merge(left, right)
print('exiting mergesort on {}'.format(L))
print('#---')
return out
mergesort([6,5,4,3,2,1])

De sortie:

---
mergesort on [6, 5, 4, 3, 2, 1]
calling mergesort on [6, 5, 4]
---
mergesort on [6, 5, 4]
calling mergesort on [6]
---
mergesort on [6]
length is 1: returning the list withouth changing
calling mergesort on [5, 4]
---
mergesort on [5, 4]
calling mergesort on [5]
---
mergesort on [5]
length is 1: returning the list withouth changing
calling mergesort on [4]
---
mergesort on [4]
length is 1: returning the list withouth changing
Merging left: [5] and right: [4]
left[i]: 5 right[j]: 4
Appending 4 to the result
result now is [4]
j now is 1
One of the list is exhausted. Adding the rest of one of the lists.
result now is [4, 5]
exiting mergesort on [5, 4]
#---
Merging left: [6] and right: [4, 5]
left[i]: 6 right[j]: 4
Appending 4 to the result
result now is [4]
j now is 1
left[i]: 6 right[j]: 5
Appending 5 to the result
result now is [4, 5]
j now is 2
One of the list is exhausted. Adding the rest of one of the lists.
result now is [4, 5, 6]
exiting mergesort on [6, 5, 4]
#---
calling mergesort on [3, 2, 1]
---
mergesort on [3, 2, 1]
calling mergesort on [3]
---
mergesort on [3]
length is 1: returning the list withouth changing
calling mergesort on [2, 1]
---
mergesort on [2, 1]
calling mergesort on [2]
---
mergesort on [2]
length is 1: returning the list withouth changing
calling mergesort on [1]
---
mergesort on [1]
length is 1: returning the list withouth changing
Merging left: [2] and right: [1]
left[i]: 2 right[j]: 1
Appending 1 to the result
result now is [1]
j now is 1
One of the list is exhausted. Adding the rest of one of the lists.
result now is [1, 2]
exiting mergesort on [2, 1]
#---
Merging left: [3] and right: [1, 2]
left[i]: 3 right[j]: 1
Appending 1 to the result
result now is [1]
j now is 1
left[i]: 3 right[j]: 2
Appending 2 to the result
result now is [1, 2]
j now is 2
One of the list is exhausted. Adding the rest of one of the lists.
result now is [1, 2, 3]
exiting mergesort on [3, 2, 1]
#---
Merging left: [4, 5, 6] and right: [1, 2, 3]
left[i]: 4 right[j]: 1
Appending 1 to the result
result now is [1]
j now is 1
left[i]: 4 right[j]: 2
Appending 2 to the result
result now is [1, 2]
j now is 2
left[i]: 4 right[j]: 3
Appending 3 to the result
result now is [1, 2, 3]
j now is 3
One of the list is exhausted. Adding the rest of one of the lists.
result now is [1, 2, 3, 4, 5, 6]
exiting mergesort on [6, 5, 4, 3, 2, 1]
#---

Un couple de façons de vous aider à comprendre ceci:

Parcourir le code dans un débogueur et regarder ce qui se passe.
Ou,
Étape à travers elle sur le papier (avec un tout petit exemple) et de regarder ce qui se passe.

(personnellement, je trouve ce genre de chose sur le papier plus instructif)

Conceptuel, il fonctionne comme ceci:
La liste d'entrée reçois haché en petits morceaux par être réduit de moitié (par exemple list[:middle] est de la première moitié). Chaque semestre est divisé par deux, encore et encore, jusqu'à ce qu'il a une longueur de moins de 2. I. e. jusqu'à ce qu'il n'est rien du tout, ou un seul élément. Ces morceaux sont ensuite combinés par la fusion de routine, en ajoutant ou en entrelaçant les 2 sous-listes pour le result liste, et par conséquent, vous obtenez une liste triée. Parce que les 2 sous-listes doivent être triées, l'ajout/interleave est rapide (O(n)) de l'opération.

La clé de la ce (à mon avis) n'est pas la fusion de la routine, c'est assez évident, une fois que vous comprenez que les entrées, il sera toujours triés. Le "truc" (j'utilise des guillemets parce que ce n'est pas une astuce, c'est de l'informatique: -) ), c'est que, afin de garantir que les données à fusionner sont triés, vous devez garder recursing vers le bas jusqu'à ce que vous arriver à une liste qui doit être triés, et c'est pourquoi vous gardez de manière récursive appel mergesort jusqu'à ce que la liste est à moins de 2 éléments de long.

La récursivité, et, par extension, de fusion et de tri, peut être non évidente lors de la première à venir à travers eux. Vous pourriez consulter un bon algorithmes livre (par exemple, DPV est disponible en ligne, gratuitement et en toute légalité), mais vous pouvez aller un long chemin en parcourant le code que vous avez. Si vous vraiment voulez obtenir dans la Stanford/Coursera algo cours seront en cours d'exécution à nouveau bientôt et il se couvre de Fusion de tri dans les moindres détails.

Si vous vraiment veulent comprendre, lire le chapitre 2 de ce livre de référence, puis jeter le code ci-dessus et ré-écrire à partir de zéro. Sérieusement.

fondamentalement, vous obtenez votre liste, vous diviser, puis à les trier, mais vous appliquez cette méthode récursive si vous vous retrouvez crève à nouveau, et encore jusqu'à ce que vous avez un trivial que vous pouvez trier facilement et puis fusionner tous les simples solutions à un tableau trié.

Comme le Wikipédia article explique, il y a de nombreuses façons d'accomplir une sorte de fusion. La manière d'accomplir une opération de fusion dépend aussi de la collection de choses pour être fusionnées, certaines collections de permettre à certains des outils que la collection a à sa disposition.

Je ne vais pas répondre à cette question à l'aide de Python, tout simplement parce que je ne peux pas l'écrire; toutefois, en prenant une partie de la "fusion de tri" algorithme semble vraiment être au cœur de la question, au sens large. Une ressource qui m'a aidé est le K. I. T. E est assez obsolète page web sur l'algorithme (écrit par un professeur), tout simplement parce que l'auteur du contenu élimine contexte des identificateurs significatifs.

Ma réponse est dérivée à partir de cette ressource.

Rappelez-vous, fusionner les algorithmes de tri de travail en démontant le fourni de collecte et de placer chacun des éléments individuels de nouveau ensemble, en comparant les pièces les unes aux autres, comme la collection est re-construit.

Ici, est le "code" (regardez à la fin pour un Java "violon"):

public class MergeSort {
/**
* @param a     the array to divide
* @param low   the low INDEX of the array
* @param high  the high INDEX of the array
*/
public void divide (int[] a, int low, int high, String hilo) {
/* The if statement, here, determines whether the array has at least two elements (more than one element). The
* "low" and "high" variables are derived from the bounds of the array "a". So, at the first call, this if 
* statement will evaluate to true; however, as we continue to divide the array and derive our bounds from the 
* continually divided array, our bounds will become smaller until we can no longer divide our array (the array 
* has one element). At this point, the "low" (beginning) and "high" (end) will be the same. And further calls 
* to the method will immediately return. 
* 
* Upon return of control, the call stack is traversed, upward, and the subsequent calls to merge are made as each 
* merge-eligible call to divide() resolves
*/
if (low < high) {
String source = hilo;
// We now know that we can further divide our array into two equal parts, so we continue to prepare for the division 
// of the array. REMEMBER, as we progress in the divide function, we are dealing with indexes (positions)
/* Though the next statement is simple arithmetic, understanding the logic of the statement is integral. Remember, 
* at this juncture, we know that the array has more than one element; therefore, we want to find the middle of the 
* array so that we can continue to "divide and conquer" the remaining elements. When two elements are left, the
* result of the evaluation will be "1". And the element in the first position [0] will be taken as one array and the
* element at the remaining position [1] will be taken as another, separate array.
*/
int middle = (low + high) / 2;
divide(a, low, middle, "low");
divide(a, middle + 1, high, "high");
/* Remember, this is only called by those recursive iterations where the if statement evaluated to true. 
* The call to merge() is only resolved after program control has been handed back to the calling method. 
*/
merge(a, low, middle, high, source);
}
}
public void merge (int a[], int low, int middle, int high, String source) {
// Merge, here, is not driven by tiny, "instantiated" sub-arrays. Rather, merge is driven by the indexes of the 
// values in the starting array, itself. Remember, we are organizing the array, itself, and are (obviously
// using the values contained within it. These indexes, as you will see, are all we need to complete the sort.  
/* Using the respective indexes, we figure out how many elements are contained in each half. In this 
* implementation, we will always have a half as the only way that merge can be called is if two
* or more elements of the array are in question. We also create to "temporary" arrays for the 
* storage of the larger array's elements so we can "play" with them and not propogate our 
* changes until we are done. 
*/
int first_half_element_no       = middle - low + 1;
int second_half_element_no      = high - middle;
int[] first_half                = new int[first_half_element_no];
int[] second_half               = new int[second_half_element_no];
//Here, we extract the elements. 
for (int i = 0; i < first_half_element_no; i++) {  
first_half[i] = a[low + i]; 
}
for (int i = 0; i < second_half_element_no; i++) {  
second_half[i] = a[middle + i + 1]; //extract the elements from a
}
int current_first_half_index = 0;
int current_second_half_index = 0;
int k = low;
while (current_first_half_index < first_half_element_no || current_second_half_index < second_half_element_no) {
if (current_first_half_index >= first_half_element_no) {
a[k++] = second_half[current_second_half_index++];
continue;
}
if (current_second_half_index >= second_half_element_no) {
a[k++] = first_half[current_first_half_index++];
continue;
}
if (first_half[current_first_half_index] < second_half[current_second_half_index]) {
a[k++] = first_half[current_first_half_index++];
} else {
a[k++] = second_half[current_second_half_index++];
}
}
}

J'ai aussi une version, ici, qui permet d'imprimer des informations utiles et fournir une représentation visuelle de ce qui se passe au-dessus. La coloration syntaxique est mieux aussi, si c'est utile.