Shuffling a sorted array

Question

If we are given a sorted array, which algorithm can we use to create an output array that has the same elements as the sorted array, but the elements must be randomly shuffled. I am looking for an algorithm that has O (n) complexity

Answer 1

Collections.shuffle(List) has a time complexity of O(n) . You can use Arrays.asList() to wrap an array so you can use this function.

What is he doing

For each element from the last to the second element, we exchange the element for a random element from the rest of the list, which includes itself, that is, it may not accidentally move the element.

 for (int i=size; i>1; i--) swap(list, i-1, rnd.nextInt(i)); 

Answer 2

you can use this code

  // Create a list List list = new ArrayList(); // Add elements to list // Shuffle the elements in the list Collections.shuffle(list); // Create an array String[] array = new String[] { "a", "b", "c" }; // Shuffle the elements in the array Collections.shuffle(Arrays.asList(array)); for (int i = 0; i < array.length; i++) { System.out.println("Count is: " + i + " letter is " + array[i]); } 

This will print something like:

Count: 0 letter is b

Count: 1 letter is

Count: 2 letters c

from http://www.exampledepot.com/egs/java.util/coll_Shuffle.html