gnome_sort.py

def gnome_sort(array):
    size = len(array)
    pos = 0
    comparisons = 0

    while pos < size:
        comparisons += 1
        if pos == 0 or array[pos] >= array[pos - 1]:
            pos += 1
        else:
            array[pos], array[pos - 1] = array[pos - 1], array[pos]
            pos -= 1

    return comparisons


def improved_gnome_sort(array):
    size = len(array)
    prev_pos = pos = 0
    comparisons = 0
    direction = 1
    while pos < size:
        comparisons += 1
        if pos == 0 or array[pos] >= array[pos - 1]:
            if direction == -1:
                pos = prev_pos + 1
                direction = 1
            else:
                pos += 1
        else:
            array[pos], array[pos - 1] = array[pos - 1], array[pos]
            if direction == 1:
                prev_pos = pos
                direction = -1
            pos -= 1
    return comparisons


input_array = list(range(10000, 0, -1))
print("It took normal gnome sort %s comparisons" % (gnome_sort(input_array)))
print(input_array)

input_array = list(range(10000, 0, -1))
print("It took improved gnome sort %s comparisons" % (improved_gnome_sort(input_array)))
print(input_array)