Hi, I'm Ataias Reis

Programmer, made in Brazil, Alma mater University of Brasilia

30 days of code in Go: Day 20 - Count inversions with Merge Sort

Hi there! Today’s post is not from HackerRank. This was an assignment that I solved for the Algorithms: Design and Analysis, Part 1 course from Coursera. The goal is to implement an algorithm presented in the videos. It was explained in high level and not considering edge cases. I first tried to do it in C++ but it was taking me more time than I wanted to spend and then I switched to Go and it was blazing fast to code. What really helped me to solve it fast was the idea of a slice in Go. Slices can be partitioned easily. For instance

  • P := a[:m], P is a slice with all elements up to index m exclusively from a
  • Q := a[m:], Q is a slice with all elements from index m inclusively to the end of a

In C++, the above operations would require me more lines of code. I would need to check the end of my vector a, declare two new vector<int> P and Q and then add half of the elements in each newly allocated vector using a for loop.

The assignment required to me to count the inversions of a given unordered list. Below is an example.

input = [6, 5, 4, 3, 2, 1]
# list after sorting
output = [1, 2, 3, 4, 5, 6]
# number of inversions found
inversions = 15

The number of inversions is maximum when the list is in reverse order like the example above. When we look at 6, we see there are five elements out of order after it. Then looking at 5 we see four elements out of order after it. In the end, we count 5+4+3+2+1 = 15 inversions for the example. The formula for the maximum number of inversions in a list of integers of size $n$ is $$f(n) = \left(\begin{array}{c}n\\ 2\end{array}\right) = \frac{n(n-1)}{2}.$$

My solution is presented below and it requires the first input to be N, the number of integers that will be fed to the program, and then the N integers need to be separated by \n. I just did that because the input they gave me was a text file with all numbers separated by \n.

package main

import (
  "fmt"
  "math"
)

// result is the merged list and the
// number of inversions
func merge(a []int, b []int, n0 int) ([]int, int) {
  n := 0 // number of inversions
  m := len(a) + len(b)
  result := make([]int, m)
  i := 0
  j := 0
  // print(b)
  for k := 0; k < m; k++ {
    // --- edge cases -----
    if i == len(a) {
      result[k] = b[j]
      j++
      continue
    }

    if j == len(b) {
      result[k] = a[i]
      i++
      continue
    }

    // -- general cases --
    if a[i] < b[j] {
      result[k] = a[i]
      i++
    } else {
      result[k] = b[j]
      j++
      // add number of inversions
      // for current merging
      n += len(a) - i
    }
  }

  return result, n + n0
}

func merge_sort(a []int) ([]int, int) {
  n := 0
  if len(a) > 1 {
    // divide and call merge sort
    m := int(math.Ceil(float64(len(a)) / 2.0))
    P := a[:m]
    Q := a[m:]
    result1, n1 := merge_sort(P)
    result2, n2 := merge_sort(Q)
    return merge(result1, result2, n1+n2)
  }
  return a, n
}

func main() {

  // Input file has N
  // in the first line
  // indicating how many
  // lines the file has
  N := 0
  fmt.Scanf("%d\n", &N)

  // allocate memory
  X := make([]int, N)

  for i := 0; i < N; i++ {
    fmt.Scanf("%d\n", &X[i])
  }

  // Ignore sorted list,
  // if needed just change _
  // by a name
  _, n := merge_sort(X)

  fmt.Printf("#Inversions: %d\n", n)
}

Running

$ go build merge_sort.go
$ ./merge_sort < IntegerArray.txt
#Inversions: 2407905288

The main difficulties I had were the edge cases. They were not presented in class and I was having weird bugs saying I was trying to access an out of bounds element of the slice.

That’s all for this assignment, thanks for reading!

Tags
comments powered by Disqus