배열 제대로 shuffle 하기 (Fisher-Yates shffle)

일반적으로 셔플 알고리즘을 떠올리면 다음과 같은 naive solution을 생각하기 쉽다.

void LnNumber::ShuffleArray(long* arr, long count)
{
      for (int i=0;i<count;i++)
      {
            long toInx = rand() % count;
            {//swap
                  long temp = arr[i];
                  arr[toInx] = arr[i];
                  arr[i] = temp;
            }
      }
}

하지만 위 코드는 순진해보이는 겉모습과 다르게 엄청난 바이어스를 포함하고 있는데,

카드 3장의 모든 순열은 3!(=3 x 2 x 1) = 6이지만 위의 toInx를 보면 3 x 3 x 3 = 27로 6으로 나눠떨어지지 않는 경우의 수를 가지고 있다!

 

따라서 아래처럼 덜 직관적이지만 n!에 맞춘 경우의 수를 가진 코드로 수정해줘야 한다.

이 코드를 Fisher-Yates shuffle이라고 한다.

void LnNumber::ShuffleArray(long* arr, long count) {
    for (int i = count - 1; i > 0; i--) {
        long toInx = rand() % (i + 1); // 0부터 i까지의 랜덤한 인덱스(i포함)
        // swap
        long temp = arr[i];
        arr[i] = arr[toInx];
        arr[toInx] = temp;
    }
}

이코드의 toInx를 보면 카드3장의 예시에서 3 x 2 x 1 = 6 = 3!의 경우의 수를 가진다.

 

sort

가장 기본적인 sort는 Array.sort()또는 Collections.sort()를 쓰면 된다. (char[] 같은건 전자만 가능한듯?)

struct node 같은걸 쓰면서 특정 필드에 대해 소팅하고 싶으면 다음 기법을 쓰자.

class Tweet {
    Long time;
    int tweetId;
}
List<Tweet> feed;
...

//time에 대해서 sort하고 싶을때
feed.sort((t1, t2) -> t1.time.compareTo(t2.time));  
//역순을 원하면 t1, t2를 바꿔준다.
feed.sort((t1, t2) -> t2.time.compareTo(t1.time));

//약간 올드하게 아래처럼도 가능
Collections.sort(feed, new Comparator<Tweet>() {
    @Override
    public int compare(Tweet t1, Tweet t2) {
        return t1.time.compareTo(t2.time);
    }
});

여러 필드에 대해서 복잡하게 정렬해야하면 아래 방법 사용

feed.sort(Comparator.comparing((Tweet t) -> t.time)
                   .thenComparing(Comparator.comparing((Tweet t) -> t.tweetId).reversed()));