HiveBrain v1.2.0
Get Started
← Back to all entries
snippetgoMinor

Quicksort implementation in Go

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
implementationquicksortstackoverflow

Problem

Learning Go and trying to get a grip of the various concepts it uses. Following is my implementation of Quicksort (choosing last element as pivot). It takes the length of the array and the subsequent array to be sorted as user input.

package main

import "fmt"

func main() {
    var n int

    fmt.Print("Enter Size: ")
    fmt.Scan(&n)

    var slice = make([]int, n)

    for i := 0; i < n; i++ {
        fmt.Print("arr[",i,"]: ")
        fmt.Scan(&slice[i])
    }

    fmt.Print("Array: ", slice, "\n")
    quickSort(slice, 0, n - 1)
    fmt.Print("Sorted Array: ", slice)
}

func quickSort(a []int, low int, high int) {
    if(low < high) {
        p := partition(a, low, high)
        quickSort(a, low, p - 1)
        quickSort(a, p + 1, high)
    }
}

func partition(a []int, low int, high int) int {
    pivot := a[high]
    i := low
    for j := low; j < high; j++ {
        if(a[j] <= pivot) {
            swap(&a[i], &a[j])
            i += 1
        }
    }
    swap(&a[i], &a[high])
    return i
}

func swap(a, b *int) {
    temp := *a
    *a = *b
    *b = temp
}


Comments on coding style, following/avoiding language convention, use of pointers, use of slices, and overall correctness of the program will be appreciated.

Solution

Most importantly, use slices to your advantage. You do not need high and low arguments, as a slice can represent a part of a slice. For example, instead of quickSort(a, low, p - 1) you could write quickSort(a[low:p]).

Swapping can be written much more elegantly with multiple assignment: a, b = b, a

Use fmt.Printfln instead of fmt.Print("Array: ", slice, "\n"). Once you have learned printf, it is almost always clearer than concatenating strings. In this simple case fmt.Println would be appropriate as well, though.

Other than that the code is clean. It seems you have used gofmt and using int instead of uint for indices is the correct choice. (Uint should only be used where absolutely needed, because it is inconvenient and error-prone to calculate with.)

Context

StackExchange Code Review Q#132822, answer score: 3

Revisions (0)

No revisions yet.