Is there an algorithm for shuffling objects in an array randomly WITHOUT utilizing Lists and Collections

Question

I want to shuffle an array of Objects in a card game simulation.

I scrolled through many posts on here and almost all of them mention transforming the array into a list, then shuffling it using an implementation of Collections.shuffle() and then transforming it back into an array.

However, since I actually want to understand what is going on while the shuffling is happening, I want to implement it myself. I wrote this code for my array of Card objects in the array unshuffledDeck[]:

Random shuffleRandom = new Random();
Card[] shuffledDeck = new Card[cardAmount];
for (int i = 0; i < cardAmount; i++) {
    int j = (int) (shuffleRandom.nextFloat() * cardAmount);
    shuffledDeck[i] = unshuffledDeck[j];
}

However, depending on the random number, multiple entries in the shuffledDeck output array can have the same Card in it, which I don't want.

Now I have thought about just adding an if statement to check if the card is already in one of the other entries, something like

Random shuffleRandom = new Random();
Card[] shuffledDeck = new Card[cardAmount];
for (int i = 0; i < cardAmount; i++) {
    int j = (int) (shuffleRandom.nextFloat() * cardAmount);
    boolean cardIsNotYetPresent = true;
    for (int k = 0; k < cardAmount; k++) {
        if (k != i && shuffledDeck[k] == unshuffledDeck[j]) {
            cardIsNotYetPresent = false;
            break;
        }
    }
    if (cardIsNotYetPresent) {
        shuffledDeck[i] = unshuffledDeck[j];
    } else {
        i--;
    }
}

, but that increase the duration drastically, which is not what I want. How would I approach this problem without adding another O(n) to the runtime of the algorithm?

Answer 1

Consider implementing the Fisher–Yates shuffle.

Instead of randomly picking an index and checking for duplicates, it works by iterating through the array from the last element to the first and swapping the current element with a randomly chosen earlier element (including itself). This ensures the time complexity is O(n).

import java.util.Random;

class Card {
    private final String suit;
    private final String rank;

    public Card(String rank, String suit) {
        this.rank = rank;
        this.suit = suit;
    }

    @Override
    public String toString() {
        return rank + " of " + suit;
    }
}

public class CardShuffler {
    public static void fisherYatesShuffle(Card[] deck) {
        Random random = new Random();
        int n = deck.length;
        for (int i = n - 1; i > 0; i--) {
            int j = random.nextInt(i + 1);
            swap(deck, i, j);
        }
    }

    private static void swap(Card[] deck, int i, int j) {
        Card temp = deck[i];
        deck[i] = deck[j];
        deck[j] = temp;
    }
    
    private static void printDeck(Card[] deck) {
        for (Card card : deck) {
            System.out.println(card);
        }
    }

    public static void main(String[] args) {
        String[] suits = {"Hearts", "Diamonds", "Clubs", "Spades"};
        String[] ranks = {"2", "3", "4", "5", "6", "7", "8", "9", "10", "Jack", "Queen", "King", "Ace"};
        Card[] deck = new Card[52];
        int index = 0;
        for (String suit : suits) {
            for (String rank : ranks) {
                deck[index++] = new Card(rank, suit);
            }
        }
        fisherYatesShuffle(deck);
        System.out.println("Shuffled Deck:");
        printDeck(deck);
    }
}

Example Output:

Shuffled Deck:
4 of Clubs
8 of Spades
2 of Diamonds
King of Hearts
3 of Diamonds
3 of Clubs
10 of Clubs
4 of Spades
10 of Hearts
Queen of Spades
6 of Hearts
8 of Diamonds
Jack of Spades
King of Spades
5 of Spades
Queen of Diamonds
3 of Hearts
Queen of Hearts
8 of Hearts
2 of Hearts
10 of Spades
2 of Clubs
Jack of Clubs
Ace of Hearts
5 of Hearts
King of Diamonds
10 of Diamonds
5 of Diamonds
7 of Clubs
9 of Clubs
5 of Clubs
6 of Spades
6 of Clubs
9 of Spades
9 of Diamonds
Jack of Hearts
2 of Spades
7 of Hearts
4 of Diamonds
King of Clubs
9 of Hearts
Ace of Diamonds
Ace of Clubs
7 of Diamonds
4 of Hearts
Ace of Spades
8 of Clubs
Queen of Clubs
Jack of Diamonds
3 of Spades
6 of Diamonds
7 of Spades

Try on JDoddle