## Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account. As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends. Of course, you can also enjoy our collection of amazing optical illusions and cool math games. If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top. If you have a website, we would appreciate a little link to BrainDen. Thanks and enjoy the Den :-) |

# Alphabetize my Dvd's

### #21

Posted 24 July 2013 - 09:06 PM

### #22

Posted 24 July 2013 - 10:35 PM

Assuming the individual is making the best moves possible and the DVDs are in the worst possible disarray, how many moves will it take to put the in alphabetical order?

"Best moves" and "worst disarray" seem interrelated.

The worst disarray for one algorithm might be duck soup for another.

(Duck soup means easy - an Americanism.)

*Vidi vici veni.*

### #23

Posted 24 July 2013 - 11:25 PM

So are you saying that there isn't a best 'worst' disarray that regardless of algorithm will produce more moves than any other such disarray when comparing effect of said algorithm on both disarrays?

### #24

Posted 25 July 2013 - 02:45 AM

Assuming the individual is making the best moves possible and the DVDs are in the worst possible disarray, how many moves will it take to put the in alphabetical order?

"Best moves" and "worst disarray" seem interrelated.

The worst disarray for one algorithm might be duck soup for another.

(Duck soup means easy - an Americanism.)

Given that the individual always rearranges the DVDs in the most efficient way possible, what is the highest number of moves it takes for any initial arrangement? (The individual may not use the same algorithm on every arrangement. In fact, one should not assume that the individual follows any one algorithm at all).

Edit: From a previous post:

You are rearranging the shelf by repeatedly taking a DVD and moving to a new spot on the shelf, and we assume that you will always rearrange the shelf in the most efficient way possible (fewest number of moves) and that you will order them left-to-right or right-to-left depending on which is faster. The problem is to find the initial order of DVDs that will result in the most number of moves.

**Edited by gavinksong, 25 July 2013 - 02:51 AM.**

### #25

Posted 25 July 2013 - 10:28 AM

http://www.sorting-algorithms.com/

There are eight columns, representing eight sorting algorithms.

There are four rows, representing four different initial orderings.

Tap the green arrows in the upper left corner.

Each cell shows a sort process that requires a certain number of moves.

If we hypothetically insert a row for EVERY initial ordering,

We would get a row of eight numbers for each of them.

The number in which cell represents the answer to the OP?

*Vidi vici veni.*

### #26

Posted 25 July 2013 - 01:07 PM

Look at the matrix of situations in this link.

http://www.sorting-algorithms.com/

There are eight columns, representing eight sorting algorithms.

There are four rows, representing four different initial orderings.

Tap the green arrows in the upper left corner.

Each cell shows a sort process that requires a certain number of moves.

If we hypothetically insert a row for EVERY initial ordering,

We would get a row of eight numbers for each of them.

The number in which cell represents the answer to the OP?

Unfortunately, no. Keep in mind that these are computer algorithms.

First of all, you can't really get a "number of moves" from a computer algorithm.

Also, not all of these algorithms follow the conditions described in the OP. For example, **quicksort **and **mergesort** recursively divide the set into subsets and then recombine them. **Heapsort** and **shellsort** repeatedly swap entries until the set is ordered. Only **insertion sort **and **bubblesort** (and perhaps **selection sort **if it is implemented unusually) make valid "moves" as they are defined in the OP, which is that an item is repeatedly taken and moved to a new place (in between two other items) - and none of these algorithms are efficient in most cases.

That being said, none of these algorithms are guaranteed to make the most efficient moves.

These computer algorithms are only optimal for sorting abstract data structures in the shortest amount of time but not in the smallest number of "moves." Making a "move" (ie. swapping or moving entries) for a computer is inexpensive and will be done often in order to simplify the problem even if it is not part of the most efficient solution (by which I mean solution with the fewest moves).

I guess a better way to think of it would be if a computer had to calculate how to optimally sort an arrangement of physical items where making a "move" was extremely expensive. For example, if we were sorting heavy storage containers.

### #27

Posted 25 July 2013 - 01:22 PM

Do you agree with these notions for this problem:

1. Even sets have a max of n/2 moves to sort given the wose possible disarray of DVDs.

2. Odd sets either have n/2 +/- 1 moves to sort given the wose possible dissarray

3. WLOG, The worst possible disarray apears the reversing of dual-consecutive number where if there are k terms and k is odd the kth term goes in the middle.

Example of #3:

1-K terms where k is even

2,1 , 4,3 , 6,5 , ... , k, k-1

1-k terms where k is odd

2,1 , 4,3 , 6,,5 , ...n, n-1, k, n+2, n+1, ... k-1, k-2

**Edited by BMAD, 25 July 2013 - 01:25 PM.**

### #28

Posted 25 July 2013 - 06:52 PM

First of all, you can't really get a "number of moves" from a computer algorithm.

Umm...what? I mean, if there is a repeatable pattern that you follow in order to solve a problem, which in the case of the OP there is, then you can write a computer program to solve it (that's what programs are...repeatable steps)

From my understanding of the OP (and forgive me, because I may have missed something in the intermediate posts), the way this sort works is basically you grab a DVD, you KNOW what position it should be in, and you insert it there. So for example:

Define this as a single "move":

Look at a DVD...does it belong at the beginning of the list of DVDs? If not, take it out...shift all of the DVDs between its old position and its new position over and insert it at its correct spot.

Now the OP also says they don't care about ascending or descending order...whichever takes fewer of the above moves (but WORST case...in other words, take the WORST POSSIBLE permutation of the DVDs using the above sort, and figure out the fewest number of "moves" it would take to sort them either ascending or descending...that is the REQUIRED number of moves to ENSURE you have sorted them.)

### #29

Posted 25 July 2013 - 07:14 PM

I may have a small error in my code, I need to double check the results above...

### #30

Posted 25 July 2013 - 07:17 PM

First of all, you can't really get a "number of moves" from a computer algorithm.

Umm...what? I mean, if there is a repeatable pattern that you follow in order to solve a problem, which in the case of the OP there is, then you can write a computer program to solve it (that's what programs are...repeatable steps)

From my understanding of the OP (and forgive me, because I may have missed something in the intermediate posts), the way this sort works is basically you grab a DVD, you KNOW what position it should be in, and you insert it there. So for example:

Define this as a single "move":

Look at a DVD...does it belong at the beginning of the list of DVDs? If not, take it out...shift all of the DVDs between its old position and its new position over and insert it at its correct spot.

Now the OP also says they don't care about ascending or descending order...whichever takes fewer of the above moves (but WORST case...in other words, take the WORST POSSIBLE permutation of the DVDs using the above sort, and figure out the fewest number of "moves" it would take to sort them either ascending or descending...that is the REQUIRED number of moves to ENSURE you have sorted them.)

Spoiler for My quick and dirty algorithm

This is interesting. It seems to support the n/2-1 conjecture mentioned earlier. Is there a way to see the solution (or shifts made) to the 11 dvd problem organized like gavinksong did?

#### 0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users