current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 1 down vote favorite

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
share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

  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.

share|improve this answer
    
Thank you!! This is very helpful. –  paradasia Jul 5 '13 at 13:17
    
"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). –  tokland Jul 5 '13 at 14:39
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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