gnome sort


See On Github

Data

Contributor

Generic placeholder thumbnail

by jcla1

in go

Source Code

package gnomeSort

// Gnome sort runs in O(n^2), but if the array
// is nearly sorted already it runs in about O(n)
// http://en.wikipedia.org/wiki/Gnome_sort
func GnomeSort(arr []int) []int {
    for pos := 1; pos < len(arr); pos++ {
        if arr[pos] >= arr[pos-1] {
            continue
        } else {
            arr[pos], arr[pos-1] = arr[pos-1], arr[pos]
            if pos > 1 {
                pos -= 1
            }
        }
        pos -= 1
    }

    return arr
}
package gnomeSort

import "testing"

func TestGnomeSort(t *testing.T) {
    arrs := [][]int{[]int{-2, 1, -3, 4, -1, 2, 1, -5, 4}, []int{2, 3, 7, -5, -1, 4, -10}}

    var result []int

    for _, arr := range arrs {
        result = GnomeSort(arr)
        if !isSorted(result) {
            t.Errorf("GnomeSort(%v) = %v", arr, result)
        }
    }
}

func isSorted(arr []int) bool {
    for i := 1; i < len(arr); i++ {
        if arr[i-1] > arr[i] {
            return false
        }
    }

    return true
}