Skip to content
Snippets Groups Projects

Lab8 fixmerge

2 files
+ 92
0
Compare changes
  • Side-by-side
  • Inline

Files

lab8/fix.go 0 → 100644
+ 91
0
/* Questa implementazione di mergesort non funziona.
Cercate di determinare cosa causa il problema, quindi correggete il programma.
La parte importante dell'esercizio è CAPIRE perché non funziona, non correggerlo!
Nota: il programma contiene due implementazioni della funzione di merge, ma il problema si riscontra
a prescindere dall'implementazione scelta (per cambiare la scelta modificare l'invocazione a riga 34)
*/
package main
import (
"fmt"
)
func main() {
a := []int{7, 2, 4, 3, 9, 1, 5, 6}
fmt.Println(a)
mergeSort(a)
fmt.Println(a)
}
func mergeSort(v []int) {
if len(v) ==1 {
return
}
n := len(v) / 2
mergeSort(v[:n])
mergeSort(v[n:])
merged := merge(v[:n],v[n:])
copy(v,merged)
}
func merge(a, b []int) []int {
return mergeAppend(a, b)
// return mergePassoPasso(a, b)
}
func mergeAppend(a, b []int) (res []int) {
res = make([]int, 0, len(a)+len(b))
var next int
i, j := 0, 0
for i < len(a) && j < len(b) {
if a[i] < b[j] {
next = a[i]
i++
} else {
next = b[j]
j++
}
res = append(res, next)
}
res = append(res, a[i:]...)
res = append(res, b[j:]...)
return res
}
// versione di basso livello: prea-alloca lo spazio e inserisce passo-passo ogni elemento delle slice
func mergePassoPasso(a, b []int) (res []int) {
res = make([]int, len(a)+len(b)) // alloco lo spazio necessario
i, j, k := 0, 0, 0
for i < len(a) && j < len(b) {
if a[i] < b[j] {
res[k] = a[i]
i++
} else {
res[k] = b[j]
j++
}
k++
}
if i < len(a) {
// res = append(res,a[i:]...)
// la parte rimanente di a va copiata (b esaurito)
for _, el := range a[i:] {
res[k] = el
k++
}
}
if j < len(b) {
// res = append(res,b[j:]...)
// la parte rimanente di b va copiata (a esaurito)
for _, el := range b[j:] {
res[k] = el
k++
}
}
return res
}
\ No newline at end of file
Loading