From: "(r.*n){2}" <perl2ruby@...>
Date: 2010-09-24T06:15:10+09:00
Subject: Re: Sorting problem with an Array of Arrays

On Sep 23, 4:46 pm, Jeremy Bopp <jer...@bopp.net> wrote:
> 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")

Wonder what the performance of this would be if there were 10,000
entries?