In computer science, we studied various algorythms for sorting list and arrays efficiently.
But what is the most efficient way to physically sort objects?
My problem: every work day, I have a rack of dry cleaning to sort. Each bag is numbered as to its location on my route. Many stops have multiple bags, so locating the second and subsequent bag is easier: it just has to go next to one of the previous ones for that stop.
This brings up a secondary question: is there any software out there, similar to Mapquest, that will determine what the most efficient route is for a list of addresses within a city?
Personally, I use mergesort to do real objects, with a slight modification: small enough groups are sorted directly, using (roughly) insertion sort.
In answer to your secondary question, there probably isn’t, as the traveling salesperson problem reduces to that. There might be approximation software, though; you’ll have to keep looking.
You could check out XMAP Business from Delorme. It does route planning. Not too expensive, $99 as I recall. My Church used it to plot addresses for a Christmas tree pickup fund-raiser. We did not use the route plotting feature, however, as it was easier to plot these by hand.
A more expensive option is Maptitude ($495) w/ a $10,000 route optimization add-on (Trans Cad). www.caliper.com
AWB: What differences between physical objects and objects in a computer do you think effects the efficiency of sorting?
The math is the same. The number of iterations to sort 10 real boxes is the same as the number of iterations to sort 10 ‘box objects’ in a computer.
In the real world, efficiency might be determined by the types of machines available to do it, the size or shape of the objects, etc. Those are practical concerns, and they’ll be different for everything.
AWB: first note that finding duplicate/adjacent tags is just a difficult as sorting. They are provably “the same problem” to us Computer Scientists.
The best sorting algorithm always depends on the properties of the data. There is no one best method. You have not given enough information about the keys (tag numbers). If they are (a) short, like at most 4 “important digits” (maybe 10 total digits but only the last ones vary in a given batch) and (b) in a small range like 0-9, then radix sort:
Put them in 10 piles based on the last digit.
Stack the 10 piles back into 1. The ‘8’ pile on the ‘9’ pile, the ‘7’ pile on those, etc.
Repeat the above for the next to last, then then 3rd from the last, etc. digits.
Note: do NOT start with the first digit. Obviously, the more “important digits” and the larger the range (like letters) the worse this is. If the items are already “almost sorted” then Insertionsort works best. Stay away from Shellsort. And remember, Quicksort is to sorting as Greenland is to real estate.
Me? I like a well tweaked Heapsort. But I’m a well tweaked kind of person.
This is known in computer science as the Travelling Salesman Problem and, at least when I studied CS, couldn’t be solved for the general case. You can attack it heuristically however, and the site I linked to above shows a solution for 15,112 cities in Germany. Sorry, I don’t know of any software that solves it “numerically” - perhaps Mapquest offers a “web service”? (depending what your budget is)
Lots of differences. For instance, say you had two groups of bags, each one sorted (like the last step before the final merge of a merge sort). In a computer, it’s nothing to copy the data from one array then the other, merging them into a final sorted list. But physically, it’d be completely inefficient to keep going back and forth seeing which group’s lead item is the next to go in the master group, pick it up, and hang it 20-30 feet away, then go back and see which of the groups has the next.
The data (the bag numbers, for whever asked) are simply numbers from 1 to 200 or so, directly related to my manifest’s stop numbers.
I only have half an hour to spare in sorting them.
If I had a perfect memory (which I don’t), I might try doing a sort of bubble sort: instead of swapping every time I found an item that belonged to the beginning, I’d just walk along all my bags and remember where the lowest unsorted bag was. When I reached the beginning, I’d then run back, pick up that bag, and place it at the beginning. Then I’d do the reverse: walk back and remember where the highest unsorted bag was, then place it once I reached the end.
Well, the one advantage of stoogesort is that it’s guaranteed to terminate. Course, you’re splitting hairs any time you call that an advantage.
Anyway, stoogesort only seems to show up in problem sets, so I’ll describe it. It’s a simple recursive algorithm. If you’ve got two elements, sort them directly. Otherwise, you sort the first two-thirds of the list, sort the last two-thirds of the list, and then sort the first two-thirds of the list again.
I leave it as an exercise to the reader to prove that stoogesort is correct, and superquadratic.
