Sign in to follow this  
intrest86

Analysis of People Sorting (or how to line up by age)

Recommended Posts

I was at an award banquet recently, an the presenter had everyone recieving an award get up and then arrange themselves alphabetically. Each group was rather slow, the general strategy was that that there was a mob and as people found a position which was between two people htey belonged between they would stop there. The line slowly formed form there. So what is the "optimal" strategy for them to sort themselves? Remember that this is different from normal sorting, because as the number of people of people (n) increases, so do the number of "processors". Efficiency will be measured by the total time required to perform the sort. I think it would be helpful to start with a constrained model and then relax it. If everyone starts in an unsorted line, and can only compare with/swap with one neighbor at a time, I believe the optimal strategy is to do a bubble sort like so: (Matching letters mean a pair to compare) AABBCCDD -> AABBCC -> AABBCCDD -> AABBCC -> AABBCCDD -> AABBCC -> AABBCCDD 95734123 59371423 53917243 35192734 31529374 13253947 12335497 -> 12334579 So it manages a sort in 7 steps. In this limited model, is bubble sort the best that can be done? And what model would be a better model then neighbor comparison for people sorting?

Share this post


Link to post
Share on other sites
Well, I for one know that coz my name starts with N ill be somewhere in the middle. so given an idea of the amount of people i think most people will sway firstly towards where they think theyd be. Alternatively my last name starts with B so Ill tend towards the front (or back depeneding on order) then do a per person 'sort' once im in the line.

I guess this 'guess-my-position-first' is something that could be factored into it, how i dont really know.

Share this post


Link to post
Share on other sites
I'm not sure if your parallel version of bubble sort is the best you can do for your restrictions, but you can do better if you don't force everyone to line up randomly to begin with.

With sorting people, you've got the advantage of parallelism as every person is responsible for putting themselves in the right order, but people aren't very good at dealing with complicated instructions en masse and you've got issues with working in real space. You've also got to factor in the different costs of moving and comparing. It takes more time to move from one end of a hall to the other than just swapping with a neighbour. Likewise, it takes less time to compare two names that start with different letter than if you're comparing similar surnames (Gardner with Gardener, for example). Especially in a noisy hall [smile].

I'd probably use the common sense approach by sorting everyone into smaller groups to begin with such as by their first letter (much easier if you can set this up with letters stuck to the walls to begin with). The smaller groups can get themselves sorted in order much quicker that way.

Share this post


Link to post
Share on other sites
If everyone starts in an unsorted mob, everyone can say their name aloud, allowing others to determine what person they should be behind (or if they're the first). Then, every person would move to be behind that person (or at the front of the line).

Share this post


Link to post
Share on other sites
Quote:
In this limited model, is bubble sort the best that can be done?
Yes. Consider the case where the oldest person is on the wrong end. It's not possible to get him in the front without moving up O(n) times.

Share this post


Link to post
Share on other sites
Quote:
Original post by thre3dee
I guess this 'guess-my-position-first' is something that could be factored into it, how i dont really know.

Well, if we assume a certain random distribution of names, we can use that to guess our approximate position, and also how far off we will tend to be. For simplicities sake, assume a uniform distribution of names that have been mapped onto the number range 0 = '' to 1 = 'zzzz...'. For some known number n of people, we can always approximate our position based on this by finding our name code x and going to the ~x*n position. The standard deviation for each person will be around n*x*(1-x). Basically, it will to sort the begin and end really well, but the middle will still need some good sorting.

Quote:
Original post by Trapper Zoid
You've also got to factor in the different costs of moving and comparing. It takes more time to move from one end of a hall to the other than just swapping with a neighbour. Likewise, it takes less time to compare two names that start with different letter than if you're comparing similar surnames (Gardner with Gardener, for example). Especially in a noisy hall .

I'd probably use the common sense approach by sorting everyone into smaller groups to begin with such as by their first letter (much easier if you can set this up with letters stuck to the walls to begin with). The smaller groups can get themselves sorted in order much quicker that way.

Those are some very good points, I hadn't considered the additional move cost of doing swaps further down the line then just your neighbor. And the noise in the hall is certainly an issue, everyone can't communicate with everyone at the same time.

Splitting people up initially will definately give a constant time improvement, but can we reduce the overally time complexity?

Quote:
Original post by ToohrVyk
If everyone starts in an unsorted mob, everyone can say their name aloud, allowing others to determine what person they should be behind (or if they're the first). Then, every person would move to be behind that person (or at the front of the line).

This is essentially quick-sort, with the advantage that each individual can move to the correct side of the pivot in constant time. Assuming that each subrange could quickly break apart and communicate with each other, this would be a O(log(n)) time method. Merge-sort would also get this performance, but maybe it could potentially be easier for people to do?


As an aside, the bubble sort from before could be enhanced by arranging the people in a double line, where the lines are side by side and every third step a comparison is done across the lines:


ABCD -> AABB -> AAB -> ABCD -> AABB -> AAB ->
9573 4123 1423 1243 1243 1234 1233
ABCD CCDD BCC ABCD CCDD BCC
4123 9573 5937 5397 5397 3579 4579
->
12334579

In the end it only shaves a step off of the entire process, and with educated position guessing it might have no effect at all. But I wonder if this could be extended to provide more of a benifit, such as putting everyone into a 2D grid. I haven't tried to figure out the complexity of this yet.

Share this post


Link to post
Share on other sites
After thinking about it more, the generalization is to arrange the people in a 2D grid that is close to square, and then have them alternate swapping in all 4 directions. The same as Sneftel's argument from before, the maximum distance that must be move is 2*n^(1/2) and this is a O(sqrt of n) method.

So the best so far is still the quicksort and mergesort with O(log n). Both can improve with the "guess initial position" improvement. But can we do better?

So far the people in our setup have been memory-less: what if we now give each person the ability to remember a few pieces of information that they are told during sorting? Can we do much better?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this