JavaScript-sort와 셔플 알고리즘

셔플 알고리즘 (shuffle)

자바스크립트에서의 랜덤 정렬을 위한 2가지 방법
1. sort()메소드
2. Fisher-Yates shuffle 알고리즘

1. sort() 메소드

일반적을 sort() 메소드는 오름차순 / 내림차순으로 정렬할 때 자주 사용됨.

오름차순 : 양수 값을 리턴

const arr = [1, 2, 3, 4, 5];
arr.sort((a, b) => a - b);

내림차순 : 음수 값을 리턴

const arr = [1, 2, 3, 4, 5];
arr.sort((a, b) => b - a);

그리고 random정렬(셔플)할 때도 사용할 수 있음.

아래의 예제에서 0<= Math.random < 1 에서의 0.xxxxx값을 발생시키며, 이 과정은 arr배열 인자만큼 실행됨. 발생 된 값이 매순간 랜덤하기 때문에 양수/음수 리턴되는 것이 매회마다 달라져, 랜덤정렬이 가능하다고 볼 수 있음,

const arr = [1, 2, 3, 4, 5];
arr.sort(() => Math.random() - 0.5);

문자열 정렬

test = ['apple','orange','grape','banana','kiwi'];

test.slice().sort((a,b)=>a-b)
//	['apple','orange','grape','banana','kiwi'] 변동없음

test.slice().sort((a,b)=>b-a)
//	['apple','orange','grape','banana','kiwi'] 변동없음

test.slice().sort((a,b)=>a[0].charCodeAt()-b[0].charCodeAt())
//	['apple','banana','orange','grape','kiwi'] 오름차순 정렬

test.slice().sort((a,b)=>b[0].charCodeAt()-a[0].charCodeAt())
//	['orange','kiwi','grape','banana','apple'] 내림차순 정렬

test.slice().sort((a,b)=>a.localeCompare(b))
//	['apple','banana','orange','grape','kiwi'] 오름차순 정렬

test.slice().sort((a,b)=>b.localeCompare(a))
//	['orange','kiwi','grape','banana','apple'] 내림차순 정렬

영어 뿐만 아니라 한글도 동일하게 적용된다.

2. 피셔 예이츠 셔플 알고리즘 Fisher-Yates Shuffle

sort()메소드는 모든 순열의 빈도 수가 균일하게 나오지 않기 때문에 권장되지 않음.
그 대신에 피셔 예이츠 셔플 알고리즘을 사용할 수 있으며, 더 널리 사용되고 있음.

이는 로날드 피셔와 프랭크 예이츠가 만들어낸 알고리즘으로 배열을 중복 없이 랜덤하게 섞은 후 리턴한다. 주로 게임야구/로또추첨기/카드뒤집기/음악랜덤 게임에서 사용됨.

피셔 예이츠 셔플 알고리즘은 오리지날(클래식)한 버전과 모던한 버전이 있다.

오리지날 버전의 동작과정과 코드는 다음과 같다.

1. 임의로 입력된 배열 [1, 2, 3, 4, 5]가 있다고 가정해보자.
2. 0부터 4까지의 난수를 발생시킨다.
3. (2)에서 난수가 3이 나왔다고 가정해보자.
4. 입력 배열[3]의 값을 뺀다. 그러면 입력배열은 [1, 2, 4, 5]가 된다.
5. 난수 3에 1을 더한다(난수: 4)
6. 난수 4와 입력 배열 길이에 1을 뺀 값를 비교연산 한다. 이 때 난수 4가 더 클 경우, 난수를 0으로 만들고, 난수 4가 더 작은 경우 값을 유지한다.
7. (4) - (6) 과정을 입력 배열이 빈 상태가 될 때까지 반복한다.

const fysOriginal = (arr) => {
    let roll = Math.floor(Math.random()*arr.length);
    const firstRoll = roll;
    const strikeOut = [];
    while(arr.length){
        strikeOut.push(arr.splice(roll, 1)[0]);
        roll += 1;
        if(roll >= arr.length)
          roll = 0;
    }
    return strikeOut;
}

아래 코드는 모던 버전

const fysModern = (arr) => {
  const strikeOut = [];
  while(arr.length){
    const lastIdx = arr.length-1;
    let roll = Math.floor(Math.random()*arr.length);
    let temp = arr[lastIdx];
    arr[lastIdx] = arr[roll];
    arr[roll] = temp;
    strikeOut.push(arr.pop());
  }
  return strikeOut;
}

예제

-숫자야구

// 숫자뽑기
let candidate = [1,2,3,4,5,6,7,8,9];
let chosenNum = [];
// 숫자 4개
for (let i = 0; i < 4; i++) {
// 1 - 9까지 랜덤한 숫자 빼주기, splice() 0-8번째 index
	let fourNum = [];
    fourNum = candidate.splice(Math.floor(Math.random() * (9 - i)), 1)[0];
    chosenNum.push(fourNum);
  }
 console.log(chosenNum);

-공뽑기

// while문
  const candidate = Array(45).fill().map((v, i) => i + 1);
  const shuffle = [];
  while (candidate.length > 0) {
    const random = Math.floor(Math.random() * candidate.length); // 무작위 인덱스 뽑기
    const spliceArray = candidate.splice(random, 1); // 뽑은 값은 배열에 들어 있음
    const value = spliceArray[0]; // 배열에 들어 있는 값을 꺼내어
    shuffle.push(value); // shuffle 배열에 넣기
  }
  console.log(shuffle);

// for문
  const candidate = Array(45).fill().map((v,i) => i+1);
  const shuffle = [];
  for (let i = candidate.length ; i > 0 ; i--){
    const random = Math.floor(Math.random() * i);
    const spliceArray = candidate.splice(random, 1);
    const value = spliceArray[0];
    shuffle.push(value);
 }
 console.log(shuffle);