slow sort
it's not Quicksort…
Barry Cipra introduced us to another deceptively simple idea that gives rise to challenging questions.
You have cards numbered from 1 to n. The cards are shuffled, and laid out left to right. Sort them by clicking a card that is not in the correct position. The card will move to its correct position. Continue clicking until all the cards are in the right place.
Below is an example with 5 cards.
maximizing the number of moves
Perhaps you tried to see how few moves it took for you to get the cards back in order. What is the greatest number of moves possible to sort the cards?
changing the configuration
Let's add the ability to change the starting configuration. Assuming that you are taking as many moves as possible for a given configuration, what configuration requires the most moves?
Enter a list numbers 1…n, where n is at most 8. As long as the list contains exactly the numbers 1…n in any order, it will display your cards in that order.
changing the number of cards
Sometimes it helps to reason about a problem by working with a smaller example. What can you conclude from starting with just 2 cards? 3? 4? Can you generalize?
is it possible to create a cycle?
Is it possible to find a starting configuration that after some number of moves, you find yourself back in the starting position? It turns out that is not possible, no matter how many cards you use. Can you prove that?
read more about it…
Sergi Elizalde and Peter Winkler unpack this problem in their arxiv article, Sorting by Placement and Shift.