Array shuffle in place, O(1) - perfect shuffle

May 7, 2015

Problem statement:

An array with 2n numbers, {a1,a2,a3,...,an,b1,b2,b3,...,bn}, sort them in the following order:

{a1,b1,a2,b2,....,an,bn}, and optimal solution time is O(n), and space is O(1).

有个长度为2n的数组{a1,a2,a3,...,an,b1,b2,b3,...,bn}，希望排序后{a1,b1,a2,b2,....,an,bn}，请考虑时间复杂度o(n)，空间复杂度0(1)的解法。

读了二篇文章, 感觉很好. 读懂了, 看了第二篇的例子, 明白了设计的思路. So much fun to read the those two articles, and then, understand the idea of perfect shuffle. Well spent time to enjoy the reading around 1 hour from 9:00pm - 10:13pm, May 6, 2015.

https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.09.md

And then, go through one example by reading the article:

http://blog.sina.com.cn/s/blog_604d011e0100l9bh.html

It is fun and exciting to learn something new. Definitely good experience.

Here are some notes written down by Julia:

Brute force algorithm: n=4, a1, a2, a3, a4, b1, b2, b3, b4

the order after the change: a1, b1, a2, b2, a3, b3, a4, b4

step 1: b1 is the 5th position in the original array, and then, b1 swaps with the one before, in other words, b1 swaps a4 first; and then, b1 swaps with a2; and last, b1 swaps with a2. How many swaps, 3.

Step 2: b2 is the 6th position in the original array. b2 swaps with a3, a4;

Step 3: b3 swaps with a4

Step 4: b4 is the last one, no swap.

The brute force solution time complexity is O(N^2) since (n-1)+(n-2)+..+1= 2n*(n-1).

In the year of 2004, the paper: "A Simple In-Place Algorithm for In-Shuffle" shares the idea to implement using time O(N).

Like to spend more time to read the article more carefully and then write the code.

January 18, 2016 

Review the algorithm. Julia, you should focus on brute force algorithm, learn how to do analysis to solve the problem first. Most of important, by any means, is to solve the problem first, using time complexity O(NxN) solution, O(1) space. O(1) space means that solution only consists of swapping two nodes.

Optimal solution is O(N) time, O(1) space. There is also a solution to use O(N) time, but O(N) space, called perfect shuffle.

To understand the solution, and then, also know that there is a better solution. What ideas are to support the improvement here?

Please remember ideas used in the algorithm:
Array - brute force - 1. 步步前移 2. 中间交换

Array - brute force - 完美洗牌算法/ perfect shuffle (1)/ Cycle-leader (2)