랜덤 셔플 알고리즘 - 카드 섞기.

이 것도 예전 네이버 블로그를 하면서 올렸던 건데 블로그 이사하면서 다시

 올려본다.

정말 초 간단한 카드 섞기 알고리즘 이다.

루프를 돌면서 배열의 현재 위치와 다음 위치중에 랜덤한 위치의 값을 바꿔주는것 이다.

 

 

- 예)

빨간색 블록은 현재의 인덱스 이고, 하늘색 블록은 랜덤하게 선택한 블록이다. 마지막으로 연 보라색 블록은 이미 카드섞기가 끝난 블록이다.

Input

 

1

2

3

4

5

Step 1.

 

1

2

3

4

5

Step 2.

 

2

1

3

4

5

Step 3.

 

2

4

3

1

5

Step 4.

 

2

4

1

3

5

Step 5. 현재 인덱스의 다음 인덱스가 더 이상 존재하지 않으면 종료.

 

2

4

1

5

3

 

 

 

#include <stdio.h></stdio.h>

#include <stdlib.h></stdlib.h>

#include <time.h></time.h>

 

void swap(int *A, int *B);                   // 변수를 서로 바꿔주는 함수

void randomCard(int* card, int size);   // 정수 배열을 섞는 함수

  

#define CARDSIZE 10                        // 정수 배열의 사이즈

 

int main()

{

    int Card[CARDSIZE];                     // 정수 배열 선언

    int i;                                             // 반복문에 쓰일 변수

 

    srand((unsigned int)time(NULL));    // Random Value For Seed Value Set

 

 

    for(i = 0; i < CARDSIZE; i++)           // 0~9 까지 카드를 채워준다.

    {

        Card[i] = i;

    }

    

    randomCard(Card, CARDSIZE);         // 카드를 섞어준다.

 

    for(i = 0; i < CARDSIZE; i++)              // 출력.

    {

        printf("%d ", Card[i]);

    }

    printf("\n");

    

 

}   

 

void randomCard(int* card, int size)   // 여기서 주목 해야 할 함수.

{

    int i;  // 반복문에 쓰일 변수

 

    for(i = 0; i < size; i++)

    {

        // 현재 위치의 카드와 현재 위치의 다음위치에서 랜덤하게 뽑은 카드를 바꾼다.

        swap(&card[i], &card[(rand() % (CARDSIZE - i)) + i]);   

    }

}

 

void swap(int* A, int* B)

{

    int temp;

 

    temp = *A;

    *A = *B;

    *B = temp;  

}