1
\$\begingroup\$

To implement an insertion sort that sorts an array with optional block to determine sorting order, how can I improve this code? (Seeking best practices and code correctness)

def custom_insertion_sort(arr)
  for i in (1..arr.length-1)
    curr = arr[i]
    compare = i-1
    if block_given?
      sorted = yield arr, compare, curr
    else
      sorted = arr[compare] < curr
    end
   while compare >= 0 && sorted
      arr[compare+1] = arr[compare]
      compare -= 1
      if block_given?
        sorted = yield arr, compare, curr
      else
        sorted = arr[compare] < curr
      end
    end
    arr[compare+1] = curr
  end
  arr
end
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$
  1. Your block usage yield arr, compare, curr is rather weird:

    custom_insertion_sort(array){ |_, i, j| _[i].abs > j.abs }
    

    I would do yield arr[compare], curr:

    naki_insert_sort(array){ |i, j| i.abs > j.abs }
    
  2. You may use ...n syntax instead of ..n-1

  3. You are sorting inplace, operating with an array like with a memory pointer, so you don't have to return arr from the function.

  4. Instead of writing comparision code twice you can either define lambda or put it just inside while condition.

And after a bit more golf I've got this:

def naki_insert_sort arr
    for i in (1...arr.length)
        curr = arr[compare = i]
        while 0 <= (compare -= 1) && ( block_given? ?
            yield(arr[compare], curr) :
            arr[compare] < curr
        )
            arr[compare + 1] = arr[compare]
        end
        arr[compare + 1] = curr
    end
end

But looks like Insertion sort and Ruby don't actually suit each other, because using indexes isn't functional.

\$\endgroup\$
1
  • \$\begingroup\$ "You are sorting inplace, operating with an array like with a memory pointer, so you don't have to return arr.". Indeed, but core Ruby methods tend to do this (on the other hand Python does not, to emphasise that they are in-place operations). \$\endgroup\$
    – tokland
    Jul 5, 2013 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.