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