Implementazione Merge Sort in Ruby

Community IT
1

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

2

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 :slight_smile:
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

3

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

4

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.

5

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