Julia's coding blog - Practice makes perfect: Array shuffle in place, O(1) - perfect shuffle
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.
And then, go through one example by reading the article:
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.
Read full article from Julia's coding blog - Practice makes perfect: Array shuffle in place, O(1) - perfect shuffle
No comments:
Post a Comment