Golang: transition to slice as a reference problem
I am trying to write a program that counts inversions within an array, but my array is not sorted properly due to referencing issues and thus clouding my score, even though I thought the fragments were passed by reference to Golang.
Here is my code:
package main
import (
"fmt"
)
func InversionCount(a []int) int {
if len(a) <= 1 {
return 0
}
mid := len(a) / 2
left := a[:mid]
right := a[mid:]
leftCount := InversionCount(left) //not being sorted properly due to reference issues
rightCount := InversionCount(right) //not being sorted properly due to reference issues
res := make([]int, 0, len(right)+len(left)) //temp slice to hold the sorted left side and right side
iCount := mergeCount(left, right, &res)
a = res //assigns the original slice with the temp slice values
fmt.Println(a) //a in the end is not sorted properly for most cases
return iCount + leftCount + rightCount
}
func mergeCount(left, right []int, res *[]int) int {
count := 0
for len(left) > 0 || len(right) > 0 {
if len(left) == 0 {
*res = append(*res, right...)
break
}
if len(right) == 0 {
*res = append(*res, left...)
break
}
if left[0] <= right[0] {
*res = append(*res, left[0])
left = left[1:]
} else { //Inversion has been found
count += len(left)
*res = append(*res, right[0])
right = right[1:]
}
}
return count
}
func main() {
test := []int{4,2,3,1,5}
fmt.Print(InversionCount(test))
}
What's the best way to solve this problem? I tried to do something similar to what I did with an array res
, forcing the function mergeCount
to take a reference to the array, but that seems very messy and it will give me errors.
source to share
You either need to pass a pointer to your fragment like:
func InversionCount(a *[]int) int {
if len(*a) <= 1 {
return 0
}
mid := len(*a) / 2
left := (*a)[:mid]
right := (*a)[mid:]
leftCount := InversionCount(&left) //not being sorted properly due to reference issues
rightCount := InversionCount(&right) //not being sorted properly due to reference issues
res := make([]int, 0, len(right)+len(left)) //temp slice to hold the sorted left side and right side
iCount := mergeCount(left, right, &res)
*a = res
fmt.Println(a) //a in the end is not sorted properly for most cases
return iCount + leftCount + rightCount
}
Or use copy
and change a = res
to copy(a, res)
.
source to share
Instead of mutating the slices, I would just return the functions obtained in the merge step.
Here's the code in this form, including some module-like code that compares the effective version to the naive O (N ^ 2) number.
package main
import "fmt"
// Inversions returns the input sorted, and the number of inversions found.
func Inversions(a []int) ([]int, int) {
if len(a) <= 1 {
return a, 0
}
left, lc := Inversions(a[:len(a)/2])
right, rc := Inversions(a[len(a)/2:])
merge, mc := mergeCount(left, right)
return merge, lc + rc + mc
}
func mergeCount(left, right []int) ([]int, int) {
res := make([]int, 0, len(left)+len(right))
n := 0
for len(left) > 0 && len(right) > 0 {
if left[0] >= right[0] {
res = append(res, left[0])
left = left[1:]
} else {
res = append(res, right[0])
right = right[1:]
n += len(left)
}
}
return append(append(res, left...), right...), n
}
func dumbInversions(a []int) int {
n := 0
for i := range a {
for j := i + 1; j < len(a); j++ {
if a[i] < a[j] {
n++
}
}
}
return n
}
func main() {
cases := [][]int{
{},
{1},
{1, 2, 3, 4, 5},
{2, 1, 3, 4, 5},
{5, 4, 3, 2, 1},
{2, 2, 1, 1, 3, 3, 4, 4, 1, 1},
}
for _, c := range cases {
want := dumbInversions(c)
_, got := Inversions(c)
if want != got {
fmt.Printf("Inversions(%v)=%d, want %d\n", c, got, want)
}
}
}
source to share