gnome sort


See On Github

Data

Contributor

Generic placeholder thumbnail

by jcla1

in python

Source Code

# 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
def gnome_sort(arr):
    pos = 1
    while pos < len(arr):
        if arr[pos] >= arr[pos-1]:
            pos += 1
        else:
            arr[pos], arr[pos-1] = arr[pos-1], arr[pos]
            if pos > 1:
                pos -= 1
    return arr
from gnome_sort import gnome_sort

def test_gnome_sort():
    arr = [5,4,3,2,1]
    assert gnome_sort(arr) == sorted(arr)

    arr = [1]
    assert gnome_sort(arr) == sorted(arr)

    arr = [1,2,3,4,5,6]
    assert gnome_sort(arr) == sorted(arr)

    arr = []
    assert gnome_sort(arr) == sorted(arr)

    print "All test passed!"

if __name__ == '__main__':
    test_gnome_sort()