[Guest]

Eight volumes of a science treatise are initially arranged in an arbitrary order. Anne wants to place the volumes 1,2,3,4,5,6,7 and 8 (counting from left to right) in this order. However, Anne is allowed the following two operations:

Counting from left to right, she can take a volume from either the third position, or the eighth position and place it in the first position.

Can she achieve her goal?

Edited November 2, 2009 by K Sengupta

[Guest]

Yes

[Guest]

obama!!!

yes she can!!

this is the logic behind the sort algorithm they use in C

[Guest]

Question about the mechanics? When choosing 3rd or 8th position and moving to postition 1, does the value in pos 1 swap with the moved position, 3 or 8? or do all the other numbers shift? e.g. if I start out with 7,1,2,5,8,6,4,3 and I choose position three and move it to 1 do I end up with 2,1,7,5,8,6,4,3 or do I end up with 2,7,1,5,8,6,4,3?

Thanks,

[Guest]

obama!!!

yes she can!!

this is the logic behind the sort algorithm they use in C

Discussion on C sorting by a C/C++/C#/Java/PHP programmer:

C / C++ / C# all have varying methods of sorting. The most popular sort is called a bubble sort, which utilizes a doubly linked list to take any varying type of data from a pair of identical lists that have two different exit points, and then moving them to the same entry point. The lists are connected, so any movement in the first list corresponds to movement in the second list. Essentially it's the same thing, just the two exit points are position 3 and position 8. The entry point in here is position 1. So a bubble sort (named because the sorted items essentially "float" to the top) would be the exact same thing as this, since most (well coded) bubble sorts have an exit point at the end (to make sure you are able to page every entry) and an entry point somewhere in the middle, far enough away from the beginning to have a significant halving effect without being so far out as to not be useable no matter what the size of the list is.

Edited November 2, 2009 by Medji

[Guest]

Yes.

Probably the simplest sorting algorithm is the so-called "bubble" sort, which simply makes its way through a list sequentially, swapping adjacent elements a_i and a_i+1, wherever it finds a_i > a_i+1. The process is repeated until no more exchanges occur, which could be as many as [array_size]-1 times if the largest and/or smallest element happens to be completely at the wrong extreme. It is fairly intuitive to see that it always stable, and always converges, even though it is horribly slow and inefficient, and almost never used. However, if Anne can swap the positions of any two volumes, she can eventually get them in any order she wishes using this method.

Let "A" be the operation of moving the last volume to the front, so that A(12345678) = (81234567) and let "B" be the operation of moving the third volume to the front, so that B(12345678) = (31245678). Then:

AABAABAABA(12345678) = (21345678)

Simply adding "A"s to the beginning and end allow you to swap any other two elements. Surely there's a more efficient way, but at least we know it is always possible.

[Guest]

[...] if Anne can swap the positions of any two adjacent volumes [...]