루비 정렬 (또는 알고리즘) 통계적 내용으로

Question

통계적으로 빠르게 정렬을 정렬해야합니다. 예를 들어 설명해 드리겠습니다.

배열 : [1,2,3,1,2,3,1,2,3,1,2,3,1,2,3] 1,2 개가 있습니다. , 3 X 5 내가 2의 20 %와 3의 80 %를 필요로한다고 가정합니다. 첫 번째 항목의 20 %가 2이고 그 중 80 %가 3 가지 가능한 배열입니다. :

[3,3,3,3,3,2,2,2,1,1,1,2,3,1,2,3,1,2] 
[2,2,2,3,3,3,3,3....] 
[3,2,3,2,3,3,3....] 

이런 종류의 알고리즘이 있습니까? 낮은 복잡성으로 수행 할 수 있습니까? (배열의 평균 길이는 70,000이고 숫자가 아닌 것입니다. 정렬 할 매개 변수가 두 개 이상일 것입니다.

Answer 1

어떻게 입력을 얻습니까? 1, 2, 3을 RNG를 사용하여 적절한 속도로 샘플링하는 것이 더 쉽지 않을 것입니다. 단일 어레이로 들어 오면 단일 O (n) 패스를 그룹으로 분할하여 비교할 때 너무 나쁘지 않아야합니다

Answer 2

나는이 질문을 완전히 이해하지 못하지만, 3 또는 2이 샘플에 나타날 확률을 단순히 높이려면 배열 내의 숫자 분포를 항상 바꿀 수 있어야합니다.

arr = [] 
80.times { arr << 3 } 
15.times { arr << 2 } 
5.times { arr << 1 } 

arr.shuffle.sample(10) 
=> [1, 3, 1, 3, 3, 3, 3, 2, 3, 3] 

arr.shuffle.sample(10) 
=> [3, 3, 3, 3, 3, 3, 3, 2, 3, 2] 

arr.shuffle.sample(10) 
=> [2, 3, 2, 3, 3, 3, 3, 3, 3, 2]