Mergesort qui sauve la mémoire

Question

Je prends une classe d'algorithmes et les devoirs les plus récents me bloquent vraiment. Essentiellement, l'affectation consiste à implémenter une version de tri de fusion qui n'alloue pas autant de mémoire temporaire que l'implémentation dans CLRS. Je suis censé le faire en créant seulement 1 tableau temporaire au début, et y mettre toutes les choses temporaires tout en divisant et en fusionnant.

Je devrais également noter que la langue de la classe est Lua, ce qui est important car les seules structures de données disponibles sont les tables. Ils sont comme des cartes Java dans la mesure où ils viennent en paires clé-valeur, mais ils sont comme des tableaux dans lesquels vous n'avez pas besoin d'insérer des choses par paires - si vous insérez seulement une chose, elle est traitée comme une valeur. sera ce que son index serait dans un langage avec de vrais tableaux. Au moins c'est comme ça que je le comprends, puisque je suis nouveau à Lua aussi. En outre, n'importe quoi, primitives, chaînes, objets, etc. peuvent être une clé - même des types différents dans la même table.

Quoi qu'il en soit, 2 choses qui me source de confusion:

Tout d'abord, eh bien, comment est-il fait? Est-ce que vous continuez d'écraser le tableau temporaire avec chaque récursion de division et de fusion? En second lieu, je suis vraiment confus au sujet des instructions de devoirs (je vérifie la classe gratuitement donc je ne peux pas demander n'importe quel membre du personnel). Voici les instructions:

1. Ecrire une procédure haut niveau merge_sort qui prend comme argument le rayon Ar- trier. Il doit déclarer un tableau temporaire, puis appeler merge_sort_1, une procédure de quatre arguments: Le tableau à trier, celui à utiliser comme espace temporaire tem- , et les index de début et de fin dans lesquels cet appel à merge_sort_1 devrait fonctionner.

2. Maintenant, écrivez merge_sort_1, qui calcule le point milieu de l'intervalle début-fin, et se fait un appel récursif à lui-même pour chaque moitié. Après cela, les appels fusionnent pour fusionner les deux moitiés. La procédure de fusion que vous écrivez maintenant sera une fonction du tableau permanent et du tableau temporaire, du début, du milieu et de la fin. Il maintient un index dans le tableau temporaire et indexe i, j dans chaque moitié (triée) du tableau permanent. Il doit parcourir le tableau temporaire du début à la fin, en copiant une valeur provenant de la moitié inférieure du tableau permanent ou de la moitié supérieure du tableau permanent . Il choisit la valeur à i dans la moitié inférieure si elle est inférieure ou égale à la valeur à j dans la moitié supérieure, et avance i. Il choisit la valeur à j dans la moitié supérieure si elle est inférieure à la valeur à i dans la moitié inférieure, et avance j. Une fois qu'une partie du tableau permanent est épuisée, assurez-vous de copier le reste de l'autre partie. Le manuel utilise une astuce avec une valeur infinie ∞ à évitez de vérifier si l'une ou l'autre partie est épuisée. Cependant, cette astuce est difficile à appliquer ici, puisque où le mettriez-vous? Enfin, copiez toutes les valeurs du début à la fin dans le tableau temporaire retour au tableau permanent.

numéro 2 est confus parce que je ne sais pas ce que merge_sort_1 est censé faire, et pourquoi il doit être une méthode différente de merge_sort. Je ne sais pas non plus pourquoi il faut passer les index de début et de fin. En fait, peut-être que j'ai mal lu quelque chose, mais les instructions sonnent comme merge_sort_1 ne fait pas de vrai travail.

En outre, l'affectation entière prête à confusion parce que je ne vois pas dans les instructions où la division est faite pour faire 2 moitiés du tableau original. Ou suis-je mal compris mergesort?

J'espère que j'ai fait du sens. Merci tout le monde!

Answer 1

D'abord, comment cela se fait-il? Avez-vous juste garder l'écrasement du tableau temporaire avec chaque récursion de fractionnement et fusion?

Oui, le tableau temporaire continue d'être écrasé. Le tableau temporaire est utilisé pendant la phase de fusion pour contenir les résultats de la fusion qui sont ensuite copiés dans le tableau permanent à la fin de la fusion.

numéro 2 est confus parce que j'ai aucune idée de ce que merge_sort_1 est censé faire, et pourquoi il doit être une méthode différente de merge_sort.

merge_sort_1 est le centre récursif du tri de fusion récursif. merge_sort sera seulement une fonction de commodité, créant le tableau temporaire et remplissant les positions initiales de départ et d'arrivée.

Je ne sais pas non plus pourquoi il doit être passé les index de début et de fin. En fait, peut-être que j'ai mal lu quelque chose, mais les instructions sonnent comme merge_sort_1 ne fait pas de vrai travail.

En outre, l'affectation est tout confus parce que je ne vois pas des instructions où la division est fait pour faire 2 moitiés du tableau d'origine. Ou suis-je malentendu mergesort?

La fonction récursive merge_sort_1 ne fonctionnera que sur une partie du tableau transmis. La partie sur laquelle elle travaille est définie par les index de début et de fin. Le point médian entre le début et la fin est la façon dont le tableau est divisé, puis divisé à nouveau sur les appels récursifs. Une fois les appels récursifs pour la moitié supérieure et inférieure terminés, les deux moitiés sont fusionnées dans le tableau temporaire, puis copiées dans le tableau permanent.

J'ai été en mesure d'écrire le tri de fusion dans Lua comme décrit et peut commenter mon implémentation. Il semble que les instructions aient été écrites comme s'il s'agissait de commentaires sur la mise en œuvre de l'enseignant. Il s'agit de la fonction merge_sort. Comme je l'ai dit, ce n'est qu'une fonction de commodité et je ne pense pas que ce soit la cause du problème.

-- Write a top level procedure merge_sort that takes as its argument 
-- the array to sort. 
function merge_sort(a) 
    -- It should declare a temporary array and then call merge_sort_1, 
    -- a procedure of four arguments: The array to sort, the one to use 
    -- as temporary space, and the start and finish indexes within which 
    -- this call to merge_sort_1 should work. 
    merge_sort_1(a,{},1,#a) 
end 

Answer 2

D'abord, je m'assurerais que vous compreniez le mergesort.
Regardez this explication, avec des animations de fantaisie pour vous aider à le comprendre.

Ceci est leur version de code pseudo de celui-ci:

# split in half 
m = n/2 

# recursive sorts 
sort a[1..m] 
sort a[m+1..n] 

# merge sorted sub-arrays using temp array 
b = copy of a[1..m] 
i = 1, j = m+1, k = 1 
while i <= m and j <= n, 
    a[k++] = (a[j] < b[i]) ? a[j++] : b[i++] 
    → invariant: a[1..k] in final position 
while i <= m, 
    a[k++] = b[i++] 
    → invariant: a[1..k] in final position 

Voyez comment ils utilisent b pour tenir une copie temporaire des données? Ce que votre professeur veut, c'est que vous passiez une table à utiliser pour ce stockage temporaire.

Est-ce que cela clarifie le devoir?

Answer 3

Votre principale routine de tri ressemblerait à ceci: (désolé, je ne sais pas Lua, donc je vais écrire un code Javaish)

void merge_sort(int[] array) { 
    int[] t = ...allocate a temporary array... 
    merge_sort_1(array, 0, array.length, t); 
} 

merge_sort_1 prend un tableau pour trier, certains début et la fin indexes, et un tableau à utiliser pour un espace temporaire. Il effectue les appels et les appels de diviser pour régner vers la routine merge. Notez que les appels récursifs doivent aller à merge_sort_1 et non merge_sort parce que vous ne voulez pas allouer le tableau sur chaque niveau récursif, juste une fois au début de la procédure de tri de fusion. (C'est le point entier dans la division du tri de fusion en deux routines.)

Je vais laisser à vous d'écrire une routine merge. Il devrait prendre le tableau original qui contient 2 sous-parties triées et un tableau temporaire, et trie le tableau original. La façon la plus simple de le faire serait de fusionner dans le tableau temporaire, puis de le recopier lorsque vous avez terminé.