Log in

No account? Create an account

Previous Entry | Next Entry

Office sort

This is mostly for the CS types:

Say you're in an office, and someone brings in a stack of 500 papers that needs to be sorted. How do you think they'll naturally approach the problem, and how as someone brimming with CS knowledge would you advise them to sort it?

See the comment count unavailable DW comments at http://mindstalk.dreamwidth.org/311734.html#comments



( 7 comments — Leave a comment )
Mar. 13th, 2012 01:57 pm (UTC)
I'd expect insertion sort, and I'd let them do it. A stack of papers allows enough random access for binary search *and* constant time insertion, making it n*log(n) and probably better than quick or heap sort, especially heap which requires more precise random access than you'd actually have.

Selection and bubble sort don't seem to get the same benefit from physicality.

Of course if it's a very large stack, or if there's multiple people available, some amount of split and merge would be appropriate.
Mar. 13th, 2012 04:24 pm (UTC)
I was going to say that it will depend on things like what storage facilities they have at their disposal, how long it takes them to determine ordering, and what's known about the contents of the papers. Standard sort algorithms tend to assume that the data are random over an unknown (aside from data type bounds) input space. If we know, for example, that these pages are numbered from 1-500, it's easy for a human to split them into stacks of 50 or 100 pages, sort each stack, then pile up the stacks and be done. Likewise, if a number of folders are available, then those can be used for a selection sort, whereas someone working on a small desk won't have that luxury. Considerations like trivial merging of sorted sets and foreknowledge of the nature of the input data change the nature of the problem from the standard "create a sort algorithm".
Mar. 13th, 2012 05:10 pm (UTC)
I'd generally also say 'insertion sort'. Not only is it reasonable, time-complexity-wise, it's also about as complicated a sorting algorithm as I'd care to explain to a non-CS person in a real-life application. ^_^
Mar. 14th, 2012 12:16 am (UTC)
Hah. This happens to me more work days than not. Except often with 1000 pages or so.
Mar. 14th, 2012 03:01 am (UTC)
Can you say more about how you solve it?

Over on DW tiferet expanded the space of possible problems; I'd assumed a simple alphabetical sort, a la the usual intro CS problem.
Mar. 14th, 2012 03:36 am (UTC)
It's already largely sorted alphabetically within each of twenty-odd groups of where people have been working. It needs to be sorted alphabetically within each of those same twenty-odd groups, except by where people are paid. I tend to yank and label the strays and then stick them back in when I reach their proper place.
Mar. 14th, 2012 03:43 am (UTC)
Sounds something like insertion sort, then.
( 7 comments — Leave a comment )


Damien Sullivan

Latest Month

August 2019


Powered by LiveJournal.com
Designed by Lilia Ahner