Skip to content
GitLab
Explore
Sign in
Primary navigation
Search or go to…
Project
A
Algoritmi-e-Strutture-Dati-2024-2025
Manage
Activity
Members
Labels
Plan
Issues
Issue boards
Milestones
Wiki
Code
Merge requests
Repository
Branches
Commits
Tags
Repository graph
Compare revisions
Snippets
Build
Pipelines
Jobs
Pipeline schedules
Artifacts
Deploy
Releases
Package registry
Container registry
Model registry
Operate
Environments
Terraform modules
Monitor
Incidents
Service Desk
Analyze
Value stream analytics
Contributor analytics
CI/CD analytics
Repository analytics
Model experiments
Help
Help
Support
GitLab documentation
Compare GitLab plans
GitLab community forum
Contribute to GitLab
Provide feedback
Keyboard shortcuts
?
Snippets
Groups
Projects
Show more breadcrumbs
Luca Ghirimoldi
Algoritmi-e-Strutture-Dati-2024-2025
Merge requests
!12
Lab8 fixmerge
Code
Review changes
Check out branch
Download
Patches
Plain diff
Expand sidebar
Merged
Lab8 fixmerge
lab8-fixmerge
into
main
Overview
0
Commits
2
Pipelines
0
Changes
2
Merged
Lab8 fixmerge
Luca Ghirimoldi
requested to merge
lab8-fixmerge
into
main
9 months ago
Overview
0
Commits
2
Pipelines
0
Changes
2
0
0
Merge request reports
Compare
main
main (base)
and
latest version
latest version
3f22004e
2 commits,
9 months ago
2 files
+
92
−
0
Inline
Compare changes
Side-by-side
Inline
Show whitespace changes
Show one file at a time
Files
2
lab8/fix.go
0 → 100644
+
91
−
0
View file @ 3f22004e
Edit in single-file editor
Open in Web IDE
/* 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