배열을 모든 순열(Permutation)이 같은 확률로 나오도록 섞는 알고리즘. 끝에서부터 앞으로 오며, 현재 위치의 원소를 그 앞쪽(자기 포함) 중 무작위로 고른 원소와 바꾼다.
function shuffle<T>(arr: T[]): T[] {
const a = [...arr]
for (let i = a.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1)) // 0 ≤ j ≤ i
;[a[i], a[j]] = [a[j], a[i]]
}
return a
}- 원소마다 한 번씩만 다루므로
O(n), 추가 공간 없이 제자리에서도 할 수 있다(위 예는 원본을 지키려고 복사했다) j를0 ≤ j ≤ i가 아니라 배열 전체에서 고르면 일부 순열이 더 자주 나오는 편향이 생긴다. 범위를 정확히 지키는 게 핵심이다arr.sort(() => Math.random() - 0.5)도 흔히 쓰지만 공정하지 않다. 정렬 알고리즘은 일관된 비교를 전제로 하므로 결과가 엔진과 구현에 따라 한쪽으로 치우친다(정렬 알고리즘)Math.random()은 암호학적으로 안전하지 않다. 추첨처럼 공정성이 중요한 곳에서는crypto.getRandomValues()를 쓴다
도널드 크누스가 『컴퓨터 프로그래밍의 예술』(The Art of Computer Programming)에서 소개해 크누스 셔플이라고도 부른다. 복잡도 감각은 빅오 표기법.