From: Jeremy Bopp <jeremy@...>
Date: 2010-09-24T05:46:53+09:00
Subject: Re: Sorting problem with an Array of Arrays

On 9/23/2010 9:20 AM, Paul wrote:
> The arrays represent timesheet records for work done.  Each person on
> the crew submits their records but sometimes they work on projects
> with others.  The majority of the record labels will be for a single
> person (e.g. the ABC-*) but from time to time a different label will
> show up (AAA, DEF, ...) because they worked a project with someone
> else.
> 
> The ruby script I have goes through the list of records and looks for
> double-bookings and other mistakes made during data entry.  For
> example, sometimes someone writes 10 PM when it was 10 AM.  That's why
> the label order is primary - it represents the order in which the jobs
> happened.  The timestamps themselves might be wrong.
> 
> However, when a new/different label appears, the "best guess" scenario
> is to insert it into the list according to timestamp and rerun the
> analysis to check that the timestamps are correct (no double-bookings,
> etc.)
> 
> I wrote a method that does a recursive analysis on the data using 2
> separately sorted arrays - one by label and one by timestamp.  It's
> weird and a bit complex but it works.  If I could find a way to sort
> the data properly in the first place, then I can simplify the code
> checking that takes place after it.

What you appear to be describing is actually an ordered insert operation
rather than a strict sort operation.  Array#sort is abstracted such that
you cannot know at any given time what is already sorted in your array,
so you cannot conditionally change your primary sort key from label to
timestamp based upon what is currently the last entry of the sorted array.

You need to define a custom insert function.  Beware that your
description of labels and how they "change" is ambiguous, so you may
need to modify the label comparison logic in the function to capture
what it really means to have different labels:

def special_insert(arr, new_item)
  if arr.empty? || new_item[0] == arr.last[0] then
    # If the array is empty or the label of the new item is the same
    # as the label of the last item in the array, append the new item
    # to the array.
    arr << new_item
  else
    # Otherwise, insert the new item by its timestamp.
    idx = arr.index { |item| new_item[1] < item[1] }
    if idx.nil? then
      # The new item is the oldest, so append it.
      arr << new_item
    else
      # Otherwise, insert the new item before the first item younger
      # than it is.
      arr.insert(idx, new_item)
    end
  end
end

unsorted_arr = [
  ["AAA-1", 1271862000, 2],
  ["ABC-1", 1271768400, 2],
  ["ABC-2", 1271773800, 1],
  ["ABC-3", 1271863200, 2],
  ["ABC-4", 1271869200, 2],
  ["DEF-1", 1271772000, 1]
]

sorted_arr = []

unsorted_arr.each do |item|
  special_insert(sorted_arr, item)
end

puts sorted_arr.collect { |item| "[#{item.join(", ")}]" }.join("\n")