sorting.cr

class BaseSort
  def less(v : Comparable, w : Comparable) : Bool
    return v < w
  end

  def exchange(a : Array(Comparable), i : Int, j : Int)
    t = a[i]
    a[i] = a[j]
    a[j] = t
  end

  def show(array : Enumerable)
    array.each do |value|
      puts "#{value} "
    end
    puts ""
  end

  def is_sorted?(elements : Enumerable)
    elements.each_with_index do |element, index|
      # puts "#{element}, #{elements[index - 1]}"
      if index > 0 && less(element, elements[index - 1])
        return false
      end
    end

    return true
  end
end

class SelectionSort < BaseSort
  def sort(elements : Array(Comparable))
    elements.each_with_index do |outer, i|
      min = i
      elements.each_with_index do |inner, j|
        min = j if (less(elements[min], elements[j]))
        exchange(elements, i, min)
      end
    end
  end
end

class InsertionSort < BaseSort
  def sort(elements : Array(Comparable))
    len = elements.size
    elements.each_with_index do |outer, i|
      j = i
      while (j > 0 && less(elements[j], elements[j - 1]))
        exchange(elements, j, j - 1)
        j -= 1
      end
    end
  end
end

class ShellSort < BaseSort
  def sort(elements : Array(Comparable))
    length = elements.size
    h = 1
    while (h < length / 3)
      h = 3 * h + 1
    end

    while (h >= 1)
      i = h
      while (i < length)
        j = i
        while (j >= h && less(elements[j], elements[j - h]))
          exchange(elements, j, j - h)
          j -= h
        end

        i += 1
      end
      h = h / 3
    end
    elements
  end
end

# list = [1, 2, 3]
list = [15, 23, 23, 98, 223, 88, 810, 19, 73, 55]

selection = SelectionSort.new
insertion = InsertionSort.new
shell = ShellSort.new

sorted_selection = selection.sort(list)
sorted_insertion = insertion.sort(list)
sorted_shell = shell.sort(list)

pp list

pp sorted_selection
pp sorted_insertion
pp sorted_shell

maybe you can check this one in ruby if you need inspiration https://gist.github.com/Nephos/d146e4d8b649a823e75ed56048d8af3c

I think there is no bug, but I did not test everything

plus: L65: you can use an iterator h..length
plus: in exchange, why not using pointers + xor