2
\$\begingroup\$

I'm new to Go, so I implemented a few sorting algorithms for practice. For example, I have an in-place insertion sort, and a bubble sort:

func bubbleSort(arr []int) {
   for i := 1; i < len(arr); i++ {
      if arr[i] < arr[i - 1] {
            tmp := arr[i - 1]
            arr[i - 1] = arr[i]
            arr[i] = tmp
            i = 0
      }
   }
}

func insertionSort(arr []int) {
   for i := 0; i < len(arr); i++ {
      for j := 0; j < i; j++ {
         if arr[j] > arr[i] {
           tmp := arr[j]
           arr[j] = arr[i]
           arr[i] = tmp
         }
      }
   }
}

However, when I went to implement merge sort, I found it most natural to use return values, because I couldn't seem to find a clean way to merge the results in place. Is there a good way to do this in Go, and would it even make sense to do so in-place? Or would it lead to difficulties when attempting to move to a concurrent implementation using goroutines? Code:

func merge(pt1 []int, pt2 []int) []int {
   totalLen := len(pt1) + len(pt2)
   arr := []int{}

   for i := 0; i < totalLen; i++ {
      // remove the smallest from the 2 slices and add it to the final
      if pt1[0] < pt2[0] {
         arr = append(arr, pt1[0])
         pt1 = pt1[1:]
      } else {
         arr = append(arr, pt2[0])
         pt2 = pt2[1:]
      }

      // break if a slice has been emptied
      if len(pt1) == 0 || len(pt2) == 0 {
         break
      }
   }

   arr = append(arr, pt1...)
   return append(arr, pt2...)
}

// merge sort algorithm
func mergeSort(arr []int) []int {
   arrLen := len(arr)

   if arrLen > 1 {
      pt1 := mergeSort(arr[arrLen/2:])
      pt2 := mergeSort(arr[:arrLen/2])
      arr = merge(pt1, pt2)
   }

   return arr
}

Any general style tips are also greatly appreciated (link to full code).

\$\endgroup\$
  • \$\begingroup\$ Can you provide full code of example for running? Or add link to playground. \$\endgroup\$ – user110702 Dec 23 '17 at 6:22
  • \$\begingroup\$ Just added a link to a gist; was getting an internal server error when trying to share a go playground. \$\endgroup\$ – treyhakanson Dec 23 '17 at 14:58
1
\$\begingroup\$

I'm not pretend to full review, but I guess better so than nothing.

  1. Golang allow swapping in one-line, so you can just do so:

    arr[i-1],arr[i] = arr[i],arr[i-1]

  2. Go does not have optional parameters nor does it support method overloading.So if you want implement more "usually" version of this sort - provide utility function which will take arguments for range:

    // merge sort algorithm
    func merge_sort(arr []int, l, r int) {
        if l < r {
            m := (l + r) / 2
            mergeSort(arr, l, m)
            mergeSort(arr, m+1, r)
            merge(arr, l, m, r)
        }
    }
    
    func mergeSort(arr []int) {
        merge_sort(arr, 0, len(arr)-1)
    }
    
  3. In your current code very often used function append, it's not very effective. As example I just re-write C code from here and get:

    func merge(arr []int, l, m, r int) {
    
        i := 0
        j := 0
        k := 0
    
        n1 := m - l + 1
        n2 := r - m
        L := make([]int, n1)
        R := make([]int, n2)
        for i < n1 {
            L[i] = arr[l+i]
            i++
        }
        for j < n2 {
            R[j] = arr[m+1+j]
            j++
        }
    
        i = 0
        j = 0
        k = l
    
        for i < n1 && j < n2 {
            if L[i] <= R[j] {
                arr[k] = L[i]
                i++
            } else {
                arr[k] = R[j]
                j++
            }
            k++
        }
    
        for i < n1 {
            arr[k] = L[i]
            i++
            k++
        }
    
        for j < n2 {
            arr[k] = R[j]
            j++
            k++
        }
    }
    
  4. About concurrent implementation - read this question and answers and this one.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.