gnome sort


See On Github

Data

Contributor

Generic placeholder thumbnail

by jcla1

in ruby

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 < arr.length
        if arr[pos] < arr[pos-1]
            arr[pos], arr[pos-1] = arr[pos-1], arr[pos]
            if pos > 1
                pos -= 1
            end
        else
            pos += 1
        end
    end
    arr
end

require_relative "./gnome_sort"

describe "#gnome_sort" do
  it "Sorts empty array" do
    arr = []
    gnome_sort(arr).should eq(arr)
  end

  it "Returns unchanged array with 1 element" do
    arr = [1]
    gnome_sort(arr).should eq(arr)
  end

  it "Sorts array" do
    arr = [9, 4, 6, -2, 6, -10, 592, 41]
    gnome_sort(arr).should eq(arr.sort)
  end
end