Selection sort algorithm with increasing/decreasing sort options

Question

I am running through some traditional algorithms in Go, and I was hoping to get feedback on efficiency and optimization.

Below is a basic selection sort algorithm that takes a parameter to dictate increasing, or decreasing order.

// SelectionSort
// in: A = {31, 41, 59, 26 , 41, 58}
//
// Increasing order
// out: A = {26, 31, 41, 41, 58, 59}

// Illustration:
// 31 | 41 | 59 | 26 | 41 | 58
// 31 | 41 | 59 | 26 | 41 | 58
// 31 | 41 | 59 | 26 | 41 | 58
// 26 | 31 | 41 | 59 | 41 | 58
// 26 | 31 | 41 | 41 | 59 | 58
//
// Decreasing order
// out: A = {59, 58, 41, 41, 31, 26}
//
// Illustration:
// 31 | 41 | 59 | 26 | 41 | 58
// 41 | 31 | 59 | 26 | 41 | 58
// 59 | 41 | 31 | 26 | 41 | 58
// 59 | 41 | 31 | 26 | 41 | 58
// 59 | 41 | 41 | 31 | 26 | 58
// 59 | 58 | 41 | 41 | 31 | 26
package main

import (
    "fmt"
)

// Function that performs a selection sort.
// Second parameter specifies increasing or decreasing order.
func SelectionSort(A []int, S string) []int {
    for i := range A {
        for j := i + 1; j < len(A); j++ {
            switch {
            case S == "increasing":
                if A[i] > A[j] {
                    A[i], A[j] = A[j], A[i]
                }
            case S == "decreasing":
                if A[i] < A[j] {
                    A[i], A[j] = A[j], A[i]
                }
            }
        }
    }
    return A
}

func main() {
    A := []int{31, 41, 59, 26, 41, 58}
    fmt.Println("Unsorted array: ", A)
    fmt.Println("Increasing sort array: ", SelectionSort(A, "increasing"))
    fmt.Println("Decreasing sort array: ", SelectionSort(A, "decreasing"))
}

Answer 1

There are a few things I would point out as being poor go style. The two different nesting loops is where I would start:

for i := range A {
    for j := i + 1; j < len(A); j++ {

The outer loop does a index-only range on the A slice, which in itself is not a problem, but logically it is for i := 0; i < len(A); i++ {. Again, this is not really a problem, other than the fact that you are looping the indexes of the slice. The problem is that in your inner loop, you make that index-loop obvious with the full-syntax loop.

I would be tempted to use a full loop for the outer loop so that the index functions on i and j are obvious.

The other thing I would suggest is that you supply a function for the S parameter, instead of a string.

While mentioning parameters, it is not common practice to use upper-case parameter names. These parameters are never exported, so should be lower-case initial, and mixedCase for multi-word names.

If you supply a function for the sort order, then your sort function is improved as well. Consider:

func SelectionSort(data []int, ordered func(int, int) bool) []int {
    for i := 0; i < len(data); i++ {
        for j := i + 1; j < len(data); j++ {
            if !ordered(data[i], data[j]) {
                data[i], data[j] = data[j], data[i]
            }
        }
    }
    return data
}

Now, you can call that code with something like:

increasing := func(a, b int) bool {
    return a <= b
}

decreasing := func(a, b int) bool {
    return a > b
}

data := []int{31, 41, 59, 26, 41, 58}
fmt.Println("Increasing sort array: ", SelectionSort(data, increasing))
....

Answer 2

You've already received two answers which reviewed your code for efficiency and style.

You may also want to consider how Go experts write idiomatic, efficient code. Read the code for the Go standard library packages (Packages - The Go Programming Language) written by Rob (a Go language author) and Russ (the principal author of the Go gc compiler and tool chain) for examples.

Here's an example of Go code for a basic selection sort algorithm (benchmarked as peterSO):

package main

import "fmt"

// Sort Order
type SortOrder bool

const (
    // Sort Order
    SortAsc SortOrder = false    // Ascending
    SortDsc SortOrder = !SortAsc // Descending
)

// SelectionSort sorts the array a into the order specified by order.
// The selection sort algorithm is an in-place comparison sort
// with O(n*n) time complexity.
func SelectionSort(a []int, order SortOrder) {
    for i, x := range a[:len(a)-1] {
        k := i
        for j, y := range a[i+1 : len(a)] {
            // For descending order, we tolerate exchanging equal keys.
            if order == (x <= y) {
                // out of order
                k = i + 1 + j
                x = y
            }
        }
        a[k], a[i] = a[i], x
    }
}

func main() {
    for _, order := range []SortOrder{SortAsc, SortDsc} {
        a := []int{31, 41, 59, 26, 41, 58}
        fmt.Println(a)
        SelectionSort(a, order)
        fmt.Println(a)
    }
}

Output:

[31 41 59 26 41 58]
[26 31 41 41 58 59]
[31 41 59 26 41 58]
[59 58 41 41 31 26]

Go uses the testing package to write tests and benchmarks. These are the results for benchmarks of the various selection sort functions. Each benchmark sorts an array of 1,024 random integers from descending to ascending order and then sorts it from ascending to descending order.

$ go test -bench=. -run=NONE
BenchmarkFr00z               200       6111019 ns/op
BenchmarkRolfl               500       3168927 ns/op
BenchmarkIcza               1000       1382537 ns/op
BenchmarkPeterSO            2000        740341 ns/op
$

The delta from fr00z for rolfl, icza, and peterSO is -48.14%, -77.38%, and -87.89% respectively. The delta to peterSO from rolfl and icza is -76.64% and -46.45% respectively.

Comments should conform to godoc documentation tool standards: Godoc: documenting Go code. Provide explanatory comments that clarify, not duplicate, code.

The Go language provides facilities to hide package, function, and method implementation details from package users. For users, the sort order is not type bool nor type func(x , y int) bool; it's type SortOrder. If we want to change the implementation, we can simply redefine the SortOrder type and the implementation.

For example, go from a boolean implementation,

// Sort Order
type SortOrder bool

const (
    // Sort Order
    SortAsc SortOrder = false    // Ascending
    SortDsc SortOrder = !SortAsc // Descending
)

func SelectionSort(a []int, order SortOrder) {
    // ...
    if order == (x <= y) {
    // ...
}

to a function implementation,

// Sort Order
type SortOrder func(x, y int) bool

// Sort Order
func SortAsc(x, y int) bool { return x >= y } // Ascending
func SortDsc(x, y int) bool { return x <= y } // Descending

func SelectionSort(a []int, order SortOrder) {
    // ...
    if order(x, y) {
    // ...
}

Now, to use the function implementation, user packages can simply, without change, be recompiled using the Go tool chain.

The primary control structure is nested loops:

for i, x := range a[:len(a)-1] {
    for j, y := range a[i+1 : len(a)] {
        // ...
    }
}

which use the idiomatic, efficient range form which allows the compiler to bypass some index range checks and calculate len(a)-1 once. Unless there are at least two array elements, no sort is needed. The upper limit for the outer loop is len(a)-1 not len(a).

Especially in the inner loop, avoid unnecessary address calculations, index range checks, memory accesses, and exchanges. Also, avoid inefficient comparisons.

Answer 3

As the question is already answered nicely, my answer just attempts to complete the existing one, and give a creative alternative and further tips.

Your function returns the slice. This seems nice so that you can print it immediately, but in Go it might give the wrong impression, it makes people think that it returns a slice because the sorting may be performed in a new slice, which needs to be stored. Since you sort the slice "in place", it is better if it's not returned, so people using your function will treat it like it modifies the content of the passed slice. For example the builtin append() returns the result because it may be a new slice, but sort.Ints() (which sorts a slice of ints in increasing order) does not because it sorts "in place".

The ordered() function value in rolfl's answer is a nice, flexible approach. However in this solution I will stick to just the information whether we want ascending or descending order. This is 1 bit of information, I will use a bool type for that.

Let's try to formulate when 2 elements have to be swapped inside the loops during sorting, asc = true telling if ascending order is required. Swap elements if:

• asc && a > b
• or !asc && a < b

If we look at it, a < b is the negated value of a > b (if they are equal, no need to swap). So we can rewrite the rule; swap elements if:

• asc && a > b
• or !asc && !(a > b)

So the original condition to swap elements not intuitively but is equivalent to the short form: asc == (a > b). We will use this.

As for the for loops: I will make use of for ... range loops. Using the nice slicing feature of Go, we can rewrite the inner loop so that it only iterates over the "rest" of the slice by reslicing the whole slice: s[i+1:] (slicing is efficient: it does not copy the elements, it just creates a new slice header - sharing the backing array).

Now this is how this algorithm looks like:

func SelSort(s []int, asc bool) {
    for i := range s {
        for j, b := range s[i+1:] {
            if asc == (s[i] > b) {
                s[i], s[i+j+1] = b, s[i]
            }
        }
    }
}

Note that in the outer loop we only used the index, as the value may change in the inner loop (if elements are swapped).

And now just for fun, let's also use a for ... range loop to test the 2 sorting directions. We will use a composite literal to create a slice holding 2 bool values (false, true) by only telling that the second value is true (and let the first value be initialized to its zero value which is false): []bool{1: true}

s := []int{31, 41, 59, 26, 41, 58}
for _, asc := range []bool{1: true} {
    SelSort(s, asc)
    fmt.Println(s)
}

Output (try it on the Go Playground):

[59 58 41 41 31 26]
[26 31 41 41 58 59]