Data Structure in Java

Working at MusicBest

You are planning a road trip and want to create a playlist of your favorite songs. Assume that the song titles are in an array of strings. Create a shuffle of your songs (permutation of your original songs).

Use the FisherYates shuffle algorithm that works in O(n) running time. We will use a method that creates pseudo-random numbers (see end for help) in O(1) running time.

The basic idea is to start from the last element, swap it with a randomly selected element from the whole array (including last). In the next step you will consider the array from 0 to n-2 (size reduced by 1), and repeat the process until you reach the first element.

Write a program that uses the provided Playlist.txt as input and outputs the shuffled array in a file called LastNameFirstNamePlaylist.txt.

Follow the next pseudocode:

To shuffle an array a of n elements (indices 0..n-1):

for i from n - 1 downto 1

j = random integer with 0 <= j <= i

exchange a[j] and a[i]

Create appropriate JUnits to test your program.