[자바스크립트] 08_랜덤 정렬 (shuffle)

랜덤 정렬 random sort

랜덤정렬을 숫자가 중복되지 않게 난수를 추출하는 방식으로 만들 수 있는 방법은 다양하다. 웹사이트를 테스트 서버에 구축 후 테스트를 수행하기 위해서 사용되는 Dummy 값들에 적용할 수 있다. 테스트 데이터에 적용하면 항상 다른 값들을 반환하기 때문에 테스트, QA를 수행하는데 있어 더 많은 case를 수행할 수 있다. 

 

피셔의 예이츠 셔플(fisher's Yates shuffle)

fisher의 yates 알고리즘은 노래의 랜덤 재생, 로또복권 번호처럼 무작위로 선택해 중복되지 않게 셔플 정렬하는 방식이다. 그림으로 알고리즘을 풀어본다면 다음과 같다. 

1. 랜덤한 배열을 만들려는 변수 randArr 과 임시로 사용할 tmpArr 변수가 있다고 가정한다.

2. 임의로 숫자를 추출하여 tmpArr 배열에 넣는다.

3. 루프를 돌려 randArr의 값이 없어질 때까지 실행한다.

4. 숫자가 무작위로 섞여있는 것을 확인 할 수 있다.

옛날 셔플 정렬 도표

1 2 3 4 5 6 7 8
Range(난수범위)	Roll(뽑은 숫자)	Scratch(선택되지 않은 숫자)	Result(뽑힌 숫자 배열)
1 - 8	3	1 2 4 5 6 7 8	3
1 - 7	4	1 2 4 6 7 8	3 5
1 - 6	5	1 2 4 6 8	3 5 7
1 - 5	3	1 2 6 8	3 5 7 4
1 - 4	4	1 2 6	3 5 7 4 8
1 - 3	1	2 6	3 5 7 4 8 1
1 - 2	2	2	3 5 7 4 8 1 6
3 5 7 4 8 1 6 2

 

//랜덤 숫자 만드는 함수

function tangled(int_num){

    var rand = Math.floor(Math.random() * int_num);

    return rand;

}

var randArr = [];

var tmpArr = [];

var len = 5;

// tmpArr 배열에 숫자 생성

for(i=0; i < len; i++){

    tmpArr.push(i+1);

}

var p = tangled(len); // 0 ~ 4 값 난수를 p 변수에 대입

for(j=0; j < p; j++){

    console.log("j="+j);

}

for(i=0; i < tmpArr.length-1; i++){

    randArr.push(tmpArr[p]); //randarr에 tmparr[p]값을 넣는다 

    tmpArr[p] = tmpArr[tmpArr.length-1];  //tmpArr[tmpArr.length - 1] 에 tmpArr[p]를 넣는다.

}

console.log(tmpArr);

현대적 방법 구현

셔플 정렬 도표

선택된 숫자(Roll) 자리에 선택되지 않은 숫자 목록의 마지막 숫자를 선택된 숫자 자리로 이동시킨다.

Range(난수범위)	Roll(뽑은 숫자)	Scratch(선택되지 않은 숫자)	Result(뽑힌 숫자 배열)
1 - 8	6	1 2 3 4 5 87	6
1 - 7	2	1 73 4 5 8	26
1 - 6	6	1 7 3 4 5	82 6
1 - 5	1	57 3 4	18 2 6
1 - 4	3	5 7 4	31 8 2 6
1 - 3	3	5 7	43 1 8 2 6
1 - 2	1	7	54 3 1 8 2 6

function shuffle(a) {

     var j,    //랜덤 함수넣을 변수

     var x,  //스왑 빈값 변수

     var i;  //변수

     for (i = a.length; i; i -= 1) { 

          j = Math.floor(Math.random() * i);

         x = a[i - 1];

         a[i - 1] = a[j];

         a[j] = x;

     }

}

현대적인 방법의 장점

시간 복잡성의 이론적 개선 이외에도 현대적인 방법의 주요 이점은 그것이 인플레이스(in-place) 알고리즘이라는 것이다. 정렬은 원래 방법과 같이 두 가지 컬렉션 (소스 및 대상)이 필요하지 않고 기존 컬렉션 내에서 발생한다. 현대적인 정렬을 사용하려면 2 개가 아닌 1 개만 있으면되므로 대용량 데이터 세트를 처리 할 때 유용하다. 

무작위로 항목 모음을 정렬하는 것은 컴퓨터 과학 분야에서 가장 많이 연구 된 문제 중 하나이며 Fisher-Yates 알고리즘의 최신 버전은 지속적으로 모음을 정렬하는 데 가장 효율적인 것으로 나타났다. 이 알고리즘이 정확히 무엇을하는지, 왜 그렇게 하는지를 더 잘 이해하기를 바란다.

 

 

출처

https://exceptionnotfound.net/understanding-the-fisher-yates-card-shuffling-algorithm/

https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle