The antithesis of Bartleby...

Factual Questions
1

or… help me slow the hamster wheel! (Salient points in Bold, for the TLDR crowd…)

I need help with some sort of mathematical explanation – made all the more complex because I have no real evidence that what I think is true is true…

Still interested? This could dull the brightest of bulbs, I warn you…

I have a very non-essential job these days – mostly as a file clerk. What keeps it from killing me is that I am not ever caught up – so the days pass rather quickly. I figured at one point that I was perfectly balanced at one point when I had about 6 hours worth of filing to do every day – and about two hours worth of other tasks.

Now, filing, in this position, consists of getting stacks of random papers every morning, sorting them, putting them in order, combining them with the other papers they relate to, and then putting them in the file drawers. I have noticed that **the relationship between the amount of papers to put in order and the time it takes to do it does not seem to be linear – rather, the amount of time it takes seems to rise exponentially. **

If that doesn’t make sense, it is something like – 10 forms might take 10 seconds to put in order, but 20 forms takes 25 seconds, or maybe 30. Part of what I am looking for here is the why**. I know that having more numbers to put in order means I have to look through a larger stack to find the right placement, but what is the real relationship in the numbers? Is there such a calculation?**

I am at a crucial point in this job, because I believe I might have hit a point of no-return – it may now be utterly impossible for me to keep up with the workload, let alone catch up to the towering mounds now covering my desk. My time allowed for filing has been cut to about 4 hours per day, and the amount to file has not been reduced by a similar factor – but I can’t even figure out what the proper factor might be! Is there any way to figure out, based on length of time it takes to do “x” amount of filing, how long I need to do “10X” filing?
Sorry folks, I’m a Horticulturalist, not a Mathematician…

(Oh, and I can only check back here at night – I’m not ignoring any help!)

2

A great deal of thought has gone into sorting algorithms.
Simple ones are, as you thought, proportional to n^2. More complex ones can have better best case / worst case performance.
http://www.brucemerry.org.za/manual/algorithms/sorting.html

3

Yeah, sorting algorithms get a bit fiddly to make become reasonable as the number of items grow. The problem is that efficient algorithms for computers aren’t necessarily going to be the best for a human, mostly because it will be unfeasible to accomplish unless you can lie each item out side to side, not to mention keeping pointers to particular items, or being able to recurse into subsections, etc.

Whether there’s a human sort that has a good running time, I’m not sure. I’m going to make a suggestion for a sort to try, but I would need to do some math to figure out how many iterations it would take as things expand.

Possibly the most handy trick for you to know is that if you have two sorted stacks of papers, you can merge them very easily. You place one stack on your left and one on your right. Assuming that these stacks are sorted least (at the bottom) to greatest (at the top), you take whichever has the greatest of the two and place it in a new stack in the middle. Repeat until both stacks are merged into one.

This lets you piecemeal sort smaller sections and then combine them rapidly.

For the piecemeal sort, you might try something like this:

Split
Try to place a paper
If the paper is lower than what’s on top of any of the working stacks then

  • If there are fewer than three/four stacks
    • Create a new stack with this paper at the bottom
  • Else
    • Merge all your stacks and place off to the side, and/or merge with previously finished stacks
      Else
  • Place the paper on top of whichever paper it is greater than, but is closest in value to.
    Goto Split
4

Think about it this way. You have n pieces of paper you want to put in order. You take the first piece A and it’s in order since you have no others. Now with the second piece B you must make one comparison. Does B go before or after A. With C it gets a bit more complicated. You compare it to the piece that’s now first (A or B). If you’re lucky it goes first as your done. If it goes after the first piece, you must then compare it to the second piece to see if it goes in the middle or at the end. On average if the pieces aren’t presorted at all, you make 1.5 comparisons (half of the three possible slots for it). This continues to be true. With the nth piece you make n/2 comparisions.

Therefore to sort N pieces this way it takes 0 + 1 + 1.5 + … + N/2 comparisons on average. This sum of 1 through N is N(N+1)/2. Your sum is half this or N(N+1)/4 = (N^2 + N)/4. If N is pretty large you can see the time of the task goes up approximately like the square of the number of pieces to sort.

This doesn’t take many things into consideration. For example, if the pieces are labeled with words or names and are to be sorted alphabetically, then when you come upon “zoo” you’d know to skip to the end and start there. Also there might be better ways to sort. Again if things are alphabetical, it might be better to make a quick pass tossing all the A-Es in one pile, all the F-Js into a second pile, etc, and then sort the piles separately.

5

Note that the most basic system should be no worse than quadratic and that is not at all the same thing as exponential. With quadratic, if your input size goes up by a factor of 10, the processing time goes up by a factor of 100. If you adopt a mergesort like method, the processing time only goes up by a little more than 10. (As opposed to exponential where a single extra item would increase the time by a constant factor, e.g., doubling.)

Learn to do merging right. Radix sort is good if the keys are small and such that probably is not the case in your situation.

OldGuy: I’d assume that your idea is akin to what the OP is already doing, a better method is required.

6

I would prefer not to reply to the OP.

7

:confused:

8

:smiley:

bordelond, I could explain the references, but I would prefer not to.

9

Thank you all for your input! It looks as if I had already (without knowing the terms for such things) implemented many of the sorting techniques. I’ll have to dive into the rest of the information when I get a moment. I’m going to try to mull all of this over at lunch and see if I can explain this to my bosses. Of cke a few lunches, as I have to remember what most of the simplest terms mean… I’ve been out of college for 25 years now!

Elendil’s’ Heir

Glad you got the reference! The dilemma I created for myself was not trusting Bartleby’s wisdom - I got into this position, took on every task, refined it to the most efficient method possible, and added more tasks until my plate was perfectly full - no waste, no down time… and then they started laying people off. Had I refused tasks from the beginning, I wouldn’t look like a slouch now!

10

Or… you might’ve been fired earlier. I’ve never understood why Bartleby’s boss, the narrator of the story IIRC, didn’t fire him after due warning that he’d better start carrying his fair share of the office’s workload.