# Implementazione Merge Sort in Ruby

**URL:** <https://www.ruby-forum.com/t/implementazione-merge-sort-in-ruby/163493>\
**Category:** IT\
**Created:** [March 20, 2009, 9:38pm UTC](https://www.ruby-forum.com/t/implementazione-merge-sort-in-ruby/163493 "2009-03-20T21:38:14Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![net-level](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/n/3ec8ea/32.png) [@net-level](https://www.ruby-forum.com/u/net-level)\
**Post date:** [March 20, 2009, 9:38pm UTC](https://www.ruby-forum.com/t/implementazione-merge-sort-in-ruby/163493/1 "2009-03-20T21:38:14Z")

</div>

Ciao a tutti,  
studiando algoritmi e strutture dati dal famoso libro “introduction to  
algorithms” ho pensato di implementare qualche algoritmo semplice in  
Ruby per prova, ho provato con il merge sort.  
Però il mio codice si comporta in modo strano… e visto che l’algoritmo  
è praticamente copiato dal testo magari c’è qualche meccanismo ruby che  
non mi è chiaro in generale qualcosa che mi è sfuggito.  
Nota: visto che il testo assume che gli array vanno da 1 a N ho riaperto  
la classe Array per dargli questo compotamento (forse è qui che sbaglio  
qualcosa).

Codice:

* * *

class Array  
alias :old\_slice :slice

def slice(a, b)  
puts “Errore” if a == 0 || b == 0  
old\_slice(a - 1, b)  
end

def   
puts “Errore” if i == 0  
at(i - 1)  
end

def []=(i, v)  
puts “Errore” if i == 0  
insert(i - 1, v)  
end

end

def mergeSort(l, p, r)  
if(p \< r)  
q = (p + r) / 2  
mergeSort(l, p, q)  
mergeSort(l, q + 1, r)  
merge(l, p, q, r)  
end  
end

def merge(l, p, q, r)  
sx = l.slice(p, q - p + 1)  
dx = l.slice(q + 1, r - q)  
sx \<\< 9 # il testo qui mette infinito, io faccio prove con numeri \< di  
9 quindi dovrebbe andare no?  
dx \<\< 9  
i = 1  
j = 1  
for k in (p…r)  
puts k  
if(sx[i] \<= dx[j])  
l[k] = sx[i]  
puts “#{sx[i]}-\>#{k}”  
i = i + 1  
else  
l[k] = dx[j]  
j = j + 1  
puts “#{dx[i]}-\>#{k}”  
end  
end  
end

## l = [3, 1, 2, 0] mergeSort(l, 1, l.length) puts “\n”, l

Ora la cosa strana è che come output la lista l è questa qui:

113313133120

Non solo non è ordinata ma ha pure qualche elemento di troppo, eppure  
stampando i valori di k non superano mai il valore limite.

Che può essere?  
Grazie

---

<div class="post-metadata">

**Author:** ![net-level](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/n/3ec8ea/32.png) [@net-level](https://www.ruby-forum.com/u/net-level)\
**Post date:** [March 21, 2009, 11:18am UTC](https://www.ruby-forum.com/t/implementazione-merge-sort-in-ruby/163493/2 "2009-03-21T11:18:25Z")

</div>

Ciao Matteo,

se sostituisci il metodo mergeSort con il codice qui sotto vedrai che la  
chiamata a merge aggiunge degli elementi all’array. L’errore è lì.

$indent = 0  
def mergeSort(l, p, r)  
$indent += 1  
if p \< r  
q = (p + r) / 2  
puts “#{“1”.rjust($indent)} #{l.inspect}”  
mergeSort(l, p, q)  
puts “#{“2”.rjust($indent)} #{l.inspect}”  
mergeSort(l, q + 1, r)  
puts “#{“3”.rjust($indent)} #{l.inspect}”  
merge(l, p, q, r)  
puts “#{“4”.rjust($indent)} #{l.inspect}”  
end  
$indent -= 1  
end

Il debugging a puts non è grazioso, ma ha la sua efficacia 🙂  
Nota la inspect per stampare l’array in modo leggibile e la rjust per  
mostrare il livello di ricorsione. Altra cosa: in Ruby le parentesi  
nelle if non servono per cui if(sx[i] \<= dx[j]) si può scrivere più  
semplicemente come if sx[i] \<= dx[j]

Paolo

Matteo T. wrote:

> Ciao a tutti,  
> studiando algoritmi e strutture dati dal famoso libro “introduction to  
> algorithms” ho pensato di implementare qualche algoritmo semplice in  
> Ruby per prova, ho provato con il merge sort.  
> Però il mio codice si comporta in modo strano… e visto che l’algoritmo  
> è praticamente copiato dal testo magari c’è qualche meccanismo ruby che  
> non mi è chiaro in generale qualcosa che mi è sfuggito.  
> Nota: visto che il testo assume che gli array vanno da 1 a N ho riaperto  
> la classe Array per dargli questo compotamento (forse è qui che sbaglio  
> qualcosa).
> 
> Codice:
> 
> * * *
> 
> class Array  
> alias :old\_slice :slice
> 
> def slice(a, b)  
> puts “Errore” if a == 0 || b == 0  
> old\_slice(a - 1, b)  
> end
> 
> def   
> puts “Errore” if i == 0  
> at(i - 1)  
> end
> 
> def []=(i, v)  
> puts “Errore” if i == 0  
> insert(i - 1, v)  
> end
> 
> end
> 
> def mergeSort(l, p, r)  
> if(p \< r)  
> q = (p + r) / 2  
> mergeSort(l, p, q)  
> mergeSort(l, q + 1, r)  
> merge(l, p, q, r)  
> end  
> end
> 
> def merge(l, p, q, r)  
> sx = l.slice(p, q - p + 1)  
> dx = l.slice(q + 1, r - q)  
> sx \<\< 9 # il testo qui mette infinito, io faccio prove con numeri \< di  
> 9 quindi dovrebbe andare no?  
> dx \<\< 9  
> i = 1  
> j = 1  
> for k in (p…r)  
> puts k  
> if(sx[i] \<= dx[j])  
> l[k] = sx[i]  
> puts “#{sx[i]}-\>#{k}”  
> i = i + 1  
> else  
> l[k] = dx[j]  
> j = j + 1  
> puts “#{dx[i]}-\>#{k}”  
> end  
> end  
> end
> 
> ## l = [3, 1, 2, 0] mergeSort(l, 1, l.length) puts “\n”, l
> 
> Ora la cosa strana è che come output la lista l è questa qui:
> 
> 113313133120
> 
> Non solo non è ordinata ma ha pure qualche elemento di troppo, eppure  
> stampando i valori di k non superano mai il valore limite.
> 
> Che può essere?  
> Grazie

---

<div class="post-metadata">

**Author:** ![net-level](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/n/3ec8ea/32.png) [@net-level](https://www.ruby-forum.com/u/net-level)\
**Post date:** [March 22, 2009, 9:33am UTC](https://www.ruby-forum.com/t/implementazione-merge-sort-in-ruby/163493/3 "2009-03-22T09:33:36Z")

</div>

Matteo T. wrote:

> Il ciclo che di fatto fa la fusione. Infatti commentando il ciclo o  
> anche solo le assegnazioni a l[k] il vettore viene smontato giusto e  
> torna come era prima (disordinato) ma senza elementi di troppo.  
> Il fatto è però che se stampo il valore di k va da 1 a 4 come deve  
> essere, eppure vengono aggiunti elementi.

Se ancora non l’hai fatto, ti consiglio di stampare il vettore l dopo  
ogni assegnamento, così vedrai da dove saltan fuori questi elementi  
extra.

Ho però un sospetto. Nel tuo codice c’è una

def []=(i, v)  
puts “Errore” if i == 0  
insert(i - 1, v)  
end

La insert, dice il manuale, fa:

> array.insert(index, obj…) → array
> 
> Inserts the given values before the element with the given index (which may  
> be negative).
> 
> a = %w{ a b c d }  
> a.insert(2, 99) #=\> [“a”, “b”, 99, “c”, “d”]  
> a.insert(-2, 1, 2, 3) #=\> [“a”, “b”, 99, “c”, 1, 2, 3, “d”]

Nota che il _before the element_ non è _at the element_

Non è che al posto della insert dovevi richiamare il metodo []=  
originale?

Paolo

---

<div class="post-metadata">

**Author:** ![net-level](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/n/3ec8ea/32.png) [@net-level](https://www.ruby-forum.com/u/net-level)\
**Post date:** [March 21, 2009, 2:01pm UTC](https://www.ruby-forum.com/t/implementazione-merge-sort-in-ruby/163493/4 "2009-03-21T14:01:08Z")

</div>

Paolo M. wrote:

> Ciao Matteo,
> 
> se sostituisci il metodo mergeSort con il codice qui sotto vedrai che la  
> chiamata a merge aggiunge degli elementi all’array. L’errore è lì.

Ciao ti ringrazio per la risposta, ho provato e ora vedo bene l’albero  
di ricorsione, dove stampo anche mano a mano il sotto-vettore sinistro e  
sotto-vettore destro.  
E il vettore viene ogni volta suddiviso correttamente.  
La parte di codice che è a questo punto sicuramente indagata è:

for k in p…r  
if sx[i] \<= dx[j]  
l[k] = sx[i]  
i += 1  
else  
l[k] = dx[j]  
j += 1  
end  
end

Il ciclo che di fatto fa la fusione. Infatti commentando il ciclo o  
anche solo le assegnazioni a l[k] il vettore viene smontato giusto e  
torna come era prima (disordinato) ma senza elementi di troppo.  
Il fatto è però che se stampo il valore di k va da 1 a 4 come deve  
essere, eppure vengono aggiunti elementi.

Ora di implementazioni di merge sort ne ho viste di diverse ma solo  
quella di questo libro fa la fusione con questo for così organizzato.  
Non vorrei che sia sbagliato il testo… ma mi fa strano visto che è uno  
dei testi più usati e rinomati sull’argomento. Un errore sarebbe reso  
noto subito.

---

<div class="post-metadata">

**Author:** ![net-level](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/n/3ec8ea/32.png) [@net-level](https://www.ruby-forum.com/u/net-level)\
**Post date:** [March 22, 2009, 11:19am UTC](https://www.ruby-forum.com/t/implementazione-merge-sort-in-ruby/163493/5 "2009-03-22T11:19:59Z")

</div>

Paolo M. wrote:

> Matteo T. wrote:
> 
> > Il ciclo che di fatto fa la fusione. Infatti commentando il ciclo o  
> > anche solo le assegnazioni a l[k] il vettore viene smontato giusto e  
> > torna come era prima (disordinato) ma senza elementi di troppo.  
> > Il fatto è però che se stampo il valore di k va da 1 a 4 come deve  
> > essere, eppure vengono aggiunti elementi.
> 
> Se ancora non l’hai fatto, ti consiglio di stampare il vettore l dopo  
> ogni assegnamento, così vedrai da dove saltan fuori questi elementi  
> extra.
> 
> Ho però un sospetto. Nel tuo codice c’è una
> 
> def []=(i, v)  
> puts “Errore” if i == 0  
> insert(i - 1, v)  
> end
> 
> La insert, dice il manuale, fa:
> 
> > array.insert(index, obj…) → array
> > 
> > Inserts the given values before the element with the given index (which may  
> > be negative).
> > 
> > a = %w{ a b c d }  
> > a.insert(2, 99) #=\> [“a”, “b”, 99, “c”, “d”]  
> > a.insert(-2, 1, 2, 3) #=\> [“a”, “b”, 99, “c”, 1, 2, 3, “d”]
> 
> Nota che il _before the element_ non è _at the element_
> 
> Non è che al posto della insert dovevi richiamare il metodo []=  
> originale?
> 
> Paolo

Hai proprio ragione! Facendo così:

class Array  
alias :old\_slice :slice  
alias :old\_op :[]=

def slice(a, b)  
puts “Errore” if a == 0 || b == 0  
old\_slice(a - 1, b)  
end

def   
puts “Errore” if i == 0  
at(i - 1)  
end

def []=(i, v)  
puts “Errore” if i == 0  
old\_op(i - 1, v)  
end  
end

Ora funziona.

Grazie di tutto.

Ciao