Count how unsorted an array is by number of swaps required to sort it.

unsorted.rb

def count_swaps list, &sort_block
  swaps = 0

  # Get a sorted list for comparison
  sorted = list.sort &sort_block

  # Check each elements against where they should be,
  # swapping them if necessary and counting the swaps.
  list.each_with_index do |element, index|
    next if element == sorted[index]
    swaps += 1

    # Find where the element should be and swap it into position
    should_be = list.find_index(sorted[index])
    list[index], list[should_be] = list[should_be], list[index]
  end

  swaps
end


if $0 == __FILE__
  require 'test/unit'

  class UnsortedCountTest < Test::Unit::TestCase
    def assert_unsorted count, list
      assert_equal count, count_swaps(list)
    end

    def test_empty
      assert_unsorted 0, [1]
    end

    def test_single_element
      assert_unsorted 0, [1]
    end

    def test_two_elements_sorted
      assert_unsorted 0, [2, 3]
    end

    def test_two_elements_unsorted
      assert_unsorted 1, [6, 5]
    end

    def test_three_elements_unsorted
      assert_unsorted 1, [3, 2, 1]
      assert_unsorted 2, [2, 3, 1]
    end

    def test_reversed
      assert_unsorted 50, (0..100).to_a.reverse
    end

    def test_custom_sort
      list = (0..100).to_a.reverse
      swaps = count_swaps(list) do |a, b|
        b <=> a
      end

      assert_equal 0, swaps
    end

    def test_many_elements_sorted
      assert_unsorted 0, (0..100).to_a
    end
  end
end