Shuffling an array in Java is all about randomizing the order of elements within the array and this process finds its uses in different situations such as games, statistical simulations, data processing, and cryptographic functions where random permutation or mixing of elements are necessary or required. Java provides different techniques for array shuffling, each with its own advantages, and applications accordingly.

Example 1:

Input

A[] = {1, 2, 3, 4, 5}

Output

2 5 3 1 4

Explanation

The order of elements after random shuffling is: 2 5 3 1 4

Example 2:

Input

A[] = {23, 14, 56, 45, 51}

Output

56 14 45 23 51

Explanation

The order of elements after random shuffling is: 56 14 45 23 51

Approach 1: Using Fisher Yates Shuffle Algorithm

The Fisher Yates shuffle algorithm, also known as the Knuth shuffle, is an efficient and unbiased method for shuffling arrays. It operates by iterating through the array in reverse order and swapping each element with a randomly selected element from the portion of the array that has not been shuffled yet. This process ensures that each element has an equal probability of ending up in any position within the shuffled array.

Algorithm

Step 1: Take input an array of elements to be shuffled and initialize a random number generator: Create a Random object to generate random numbers for selecting elements to swap.

Step 2: Iterate through the array in reverse order: Start iterating from the last element (array.length - 1) down to the second element (1). The loop starts from the last element because the last element doesn't need to be swapped with itself.

Step 3: In each iteration: Generate a random index (index) between 0 and the current index (i), inclusive, using the random number generator.

Step 4: Swap the element at index i with the element at the randomly selected index index. This is achieved by using a temporary variable to hold one of the elements during the swap operation.

Step 5: Continue until the entire array is shuffled: Repeat the process until all elements of the array have been shuffled. Once the shuffling process is complete, print the shuffled array.

Filename: FisherYatesShuffle.java

import java.util.Random;

public class FisherYatesShuffle {

    // Main method to demonstrate the shuffle

    public static void main(String[] args) {

        // Example array to be shuffled

        Integer[] array = {1, 2, 3, 4, 5}; // You can replace it with any array of your choice

        // Shuffling the array

        shuffleArray(array);

        // Displaying the shuffled array

        System.out.println("Shuffled Array:");

        for (Integer num : array) {

            System.out.print(num + " ");

        }

    }

    // Method to shuffle the array using Fisher-Yates algorithm

    public static void shuffleArray(Integer[] array) {

        Random rnd = new Random(); // Random number generator

        // Loop through the array from the last element to the second element

        // The loop starts from the last element because the last element doesn't need to be swapped with itself

        for (int i = array.length - 1; i > 0; i--) {

            // Generate a random index between 0 and i (inclusive)

            int index = rnd.nextInt(i + 1);

            // Swap the current element with the randomly selected element

            // Swap is performed by using a temporary variable

            int temp = array[index];

            array[index] = array[i];

            array[i] = temp;

        }

    }

}

Output:

Shuffled Array:

3 4 5 2 1

Time Complexity

The time complexity of the Fisher-Yates shuffle algorithm is O(n), where n is the number of elements in the array. The algorithm iterates through the array once, performing a constant number of operations (swapping elements) in each iteration. Since the number of operations performed is proportional to the size of the array, the time complexity is linear.

Space Complexity

The space complexity of the Fisher-Yates shuffle algorithm is O(1), indicating constant space usage. Only a constant amount of extra space is used for variables such as the loop index, the random number generator, and a temporary variable for swapping elements.

Approach 2: Using Collections.shuffle()

Shuffling an array using the Collections.shuffle() approach involves leveraging the utility methods provided by the java.util.Collections class in Java. This method is particularly convenient as it handles the shuffling process through existing library functions, simplifying the implementation and reducing the amount of boilerplate code required.

Algorithm

Step 1: Create an empty ArrayList or any other list implementation to hold the elements of the array. Iterate through the elements of the array and add them to the list.

Step 2: Once all elements are added to the list, call the Collections.shuffle() method, passing the list as an argument. The method shuffles the elements of the list using the default source of randomness.

Step 3: Convert List back to Array: If needed, convert the shuffled list back to an array. Create a new array with the same size as the original array.

Step 4: Iterate through the shuffled list and copy its elements to the new array. After shuffling, the elements of the array are randomly permuted, we can now display the shuffled array as required.

Filename: ShuffleArrayUsingCollections.java

import java.util.ArrayList;

import java.util.Collections;

import java.util.List;

public class ShuffleArrayUsingCollections {

    public static void main(String[] args) {

        Integer[] array = {1, 2, 3, 4, 5}; // Example array, change it according to your needs

        // Convert array to list

        List<Integer> list = new ArrayList<>();

        Collections.addAll(list, array);

        // Shuffle the list

        Collections.shuffle(list);

        // Convert list back to array (optional)

        list.toArray(array);

        // Display shuffled array

        System.out.println("Shuffled Array:");

        for (Integer num : array) {

            System.out.print(num + " ");

        }

    }

}

Output:

Shuffled Array:

2 4 1 3 5

Time Complexity

Converting the array to a list takes O(n) time, where n is the number of elements in the array. Shuffling the list using Collections.shuffle() also typically takes O(n) time, as it iterates through the list and performs swaps. Therefore, the overall time complexity of shuffling the array is O(n).

Space Complexity

Converting the array to a list and storing the shuffled list temporarily requires O(n) additional space. Creating the shuffled array (if needed) also requires additional space proportional to the size of the original array. Therefore, the overall space complexity of shuffling the array is O(n).

Approach 3: Using LinkedList

Using a LinkedList to shuffle an array involves leveraging the flexibility and functionality provided by the LinkedList class in Java. This approach allows us to easily add elements from the array to the linked list, shuffle the elements within the linked list, and then convert the shuffled linked list back to an array.

Algorithm

Step 1: Create a new LinkedList and iterate through each element of the array. Add each element to the LinkedList.

Step 2: Shuffle the LinkedList: Use the Collections.shuffle() method to shuffle the elements of the LinkedList. The method randomly permutes the elements of the LinkedList using the default source of randomness.

Step 3: Convert LinkedList back to Array: Create a new array with the same size as the original array. Iterate through the shuffled LinkedList.

Step 4: Copy each element from the shuffled LinkedList to the corresponding index in the new array. Once the array is shuffled, we can display the shuffled array as output.

Filename: ShuffleArrayUsingLinkedList.java

import java.util.*;

public class ShuffleArrayUsingLinkedList {

    public static void main(String[] args) {

        Integer[] array = {1, 2, 3, 4, 5}; // Example array, change it according to your needs

        // Convert array to LinkedList

        LinkedList<Integer> list = new LinkedList<>(Arrays.asList(array));

        // Shuffle the LinkedList

        Collections.shuffle(list);

        // Convert LinkedList back to array

        list.toArray(array);

        // Display shuffled array

        System.out.println("Shuffled Array:");

        for (Integer num : array) {

            System.out.print(num + " ");

        }

    }

}

Output:

Shuffled Array

2 4 1 3 5

Time Complexity

Converting the array to a LinkedList requires iterating through each element of the array once, which takes O(n) time, where n is the number of elements in the array. Shuffling the LinkedList using Collections.shuffle() also typically takes O(n) time, as it iterates through the LinkedList and performs swaps. Therefore, the overall time complexity of shuffling the array is O(n).

Space Complexity

Converting the array to a LinkedList and storing the shuffled LinkedList temporarily require O(n) additional space. Creating the shuffled array (if needed) also requires additional space proportional to the size of the original array. Therefore, the overall space complexity of shuffling the array is O(n).

Conclusion

In conclusion, shuffling an array in Java is a straightforward task with multiple available approaches. By understanding the characteristics and trade-offs of each approach, developers can choose the most suitable method for their specific needs, ensuring efficient and reliable array shuffling in their Java applications.

← Prev Next →

Shuffle an Array in Java

Approach 1: Using Fisher Yates Shuffle Algorithm

Algorithm

Approach 2: Using Collections.shuffle()

Algorithm

Approach 3: Using LinkedList

Algorithm

Conclusion