[Algorithm] Random Shuffling

Fisher-Yates Shuffle (Knuth Shuffle)

• 가장 널리 사용되고 효율적인 무작위 순열 알고리즘
• 배열의 마지막 요소부터 시작하여, 각 요소를 그 이전의 임의의 요소와 교환하는 방식으로 진행
• 시간 복잡도 : O(n) → 각 요소는 한 번씩만 처리

function fisherYatesShuffle(array) {
    for (let i = array.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [array[i], array[j]] = [array[j], array[i]];
    }
}

Inside-Out Algorithm

• Fisher-Yates Shuffle과 유사
• 차이점 : 새로운 배열에 원래 배열의 요소를 복사하면서 무작위로 요소를 교환하는 방식
• 기존의 배열을 변경하지 않고 새 배열에 순열을 생성할 때 유용
• 시간 복잡도 : O(n)

function insideOutShuffle(original) {
    const shuffled = [];
    for (let i = 0; i < original.length; i++) {
        const j = Math.floor(Math.random() * (i + 1));
        if (i !== j) shuffled[i] = shuffled[j];
        shuffled[j] = original[i];
    }
    return shuffled;
}

Sattolo's Algorithm

• 순환 순열을 생성하는 알고리즘
• 모든 결과가 정확히 하나의 순환으로 구성
• Fisher-Yates Shuffle의 변형
• 배열의 마지막 요소를 제외하고 무작위 요소와 교환
• 주로 특정 유형의 게임이나 실험에서 사용

function sattolosCycle(array) {
    for (let i = array.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * i);
        [array[i], array[j]] = [array[j], array[i]];
    }
}

Modern Algorithm

• 암호학적으로 안전한 난수 발생기를 사용하여 무작위 순열을 생성
• 보안이 중요한 애플리케이션에서 사용
• 비밀번호나 보안 키 생성에 적합
• WEB에서는 crypto 모듈 활용

function secureShuffle(array) {
    for (let i = array.length - 1; i > 0; i--) {
        const arrayBuffer = new Uint32Array(1);
        window.crypto.getRandomValues(arrayBuffer);
        const randomValue = arrayBuffer[0] / (0xffffffff + 1);
        const j = Math.floor(randomValue * (i + 1));
        [array[i], array[j]] = [array[j], array[i]];
    }
}