Skip to main content
edited tags
Link
Jamal
  • 35.2k
  • 13
  • 134
  • 238
Source Link
user44869
user44869

Implementation of merge sort and bubble sort

I'm new to Go and looking for a review of my merge sort and bubble sort implementations. What can be done better? Can my code be cleaner/clearer?

// algos.go
// (C) 2014 splashinn
// Implement two types of sorting algorithms; merge sort and bubble sort

package main

import (
    "fmt"
    "time"
    "math/rand"
)

func main() {

    var n int
    fmt.Printf("How long of an array should we sort? (≤1000) ")
    _, err := fmt.Scanf("%d", &n)
    if err != nil {
        fmt.Println("Error:", err)
        return
    }
    if n > 1000 {
        fmt.Println("Error:", n, "> 1000 - too long!")
        return
    } else if n < 1 {
        fmt.Println("Error:", n, "< 1")
        return
    }

    array := make([]int, n)
    rand.Seed(time.Now().UTC().UnixNano())

    fmt.Println("Original Array:")
    for i := range array {
        array[i] = rand.Intn(10000)
        fmt.Printf("%d\t", array[i])
    }
    fmt.Println()

    bubbleSortedArray := BubbleSort(array)

    fmt.Println("Bubble Sorted Array: ")
    for i := range bubbleSortedArray {
        fmt.Printf("%d\t", bubbleSortedArray[i])
    }
    fmt.Println()

    mergeSortedArray := MergeSort(array)

    fmt.Println("Merge Sorted Array: ")
    for i := range mergeSortedArray {
        fmt.Printf("%d\t", mergeSortedArray[i])
    }
    fmt.Println()
}

// Implementing bubble sort
func BubbleSort(inputArray []int) (sortedArray []int) {
    array := make([]int, len(inputArray))
    copy(array, inputArray)
    for i := 0; i < len(array)-1; i++ {
        for j := 0; j < len(array)-1; j++ {
            if array[j] > array[j+1] {
                // Idiomatic Go swap
                array[j], array[j+1] = array[j+1], array[j]
            }
        }
    }
    return array
}

// Implementing a top-down merge sort
// Adapted from the Merge Sort C code from Wikipedia
func MergeSort(array []int) (sortedArray []int) {
    sortedArray = make([]int, len(array), cap(array))
    splitMerge(array, sortedArray)
    return array
}

func splitMerge(A []int, B []int) {
    if(len(A) < 2) {   // if run size == 1, consider it sorted
        return
    }
    // recursively split runs into two halves until run size == 1,
    // then merge them and return back up the call chain
    iMiddle := len(A) / 2              // iMiddle = mid point
    splitMerge(A[:iMiddle], B[:iMiddle])  // split / merge left  half
    splitMerge(A[iMiddle:], B[iMiddle:])  // split / merge right half
    merge(A, B, iMiddle)  // merge the two half runs
    copy(A, B)             // copy the merged runs back to A
}

func merge(A []int, B []int, iMiddle int) {
    i0 := 0
    i1 := len(A) / 2
    iEnd := len(A)

    for j := range A {
        // If left run head exists and is <= existing right run head.
        if (i0 < iMiddle && (i1 >= iEnd || A[i0] <= A[i1])) {
            B[j] = A[i0]
            i0++  // Increment i0 after using it as an index.
        } else {
            B[j] = A[i1]
            i1++  // Increment i1 after using it as an index.
        }
    }
}