5-жды призёр ЭпоЭ и скорая Русская сортировка половинами интегралов ставок и МЫ

5-жды призёр ЭпоЭ и скорая Русская сортировка половинами интегралов ставок и МЫ


мной применяется Русская сортировка половинами интегралов ставок

для сортировки матчей по коэффициентам
чтобы ставить на крупные коэффициенты меньше
и чтобы ставить на малые коэффициенты больше

и чтобы после выигрыша понижать ставки


rusortpol50.gif


Теория в моей теме Русская сортировка половинами: человеческая сортировка быстрее в 4 раза и МЫ а здесь только визуализации малого размера:


Русская сортировка половинами важные действия

rspvip.gif

Russian sorting halves important actions visualisation 


Русская сортировка половинами все действия

rshall.gif

Russian sorting halves all actions visualization 


Визуализация и теория: 

RuSort55.gif


Думаю далее продолжу темы с ключевыми словами 

Интеграл и Логарифм и Комбинаторика и Вероятность

обобщая мои темы https://legalbet.ru/users/147331/


Чтобы ставить на крупные коэффициенты меньше
и чтобы ставить на малые коэффициенты больше 

и чтобы после выигрыша понижать ставки


Никому ничего никогда не рекомендую и всегда пишу про себя


Зато каждый призёр конкурса ЭпоЭ может создавать свои темы 


Дочитавшим до сюда вдруг интересно сравнение сортировки: 


Русская Сортировка Половинами Ускоряет Данилин
Russian Sort Halves Accelerate Danilin

ускоряющее развитие: массивы d(N) и a(N)

и действительно успешно: сортирует 100ооо за 0,22 секунды


сортирует 1000ооо за 2,2 секунды

сортирует миллион за 2,2 секунды

сортирует 1'000'000 за 2,2 секунды


'RUSSIAN sorting halves 4 part bubble
N=17539
DIM d(N), a(N), v(N), q(5)
RANDOMIZE TIMER: FOR i=1 TO N: d(i)=INT(RND * N): NEXT
FOR k=1 TO 10: PRINT d(k);: NEXT: PRINT: FOR k=N-9 TO N: PRINT d(k);: NEXT: PRINT: PRINT

start=TIMER: s=0

' ALL
summa=0: FOR i=1 TO N: summa=summa+d(i): NEXT: middle=summa/N: y=1: z=0
FOR i=1 TO N
    IF d(i) < middle THEN a(y)=d(i): y=y+1: ELSE a(N-z)=d(i): z=z+1
NEXT
q(3)=y-1
PRINT "ALL middle="; middle
FOR k=1 TO 10: PRINT a(k);: NEXT: PRINT: FOR k=N-9 TO N: PRINT a(k);: NEXT: PRINT: PRINT

'1 FROM 2
summa=0: FOR i=1 TO q(3): summa=summa+a(i): NEXT: middle=summa/q(3): y=1: z=0
PRINT "1 FROM 2="; middle, "1 ..."; q(3)
FOR i=1 TO q(3)
    IF a(i) < middle THEN v(y)=a(i): y=y+1: ELSE v(q(3)-z)=a(i): z=z+1
NEXT
FOR k=1 TO 10: PRINT v(k);: NEXT: PRINT: FOR k=q(3)-9 TO q(3): PRINT v(k);: NEXT: PRINT: PRINT
q(2)=y-1

'2 FROM 2
summa=0: FOR i=q(3)+1 TO N: summa=summa+a(i): NEXT: middle=summa/(1+N-q(3)): y=q(3): z=0
PRINT "2 FROM 2="; middle, q(3)+1; "..."; N
FOR i=q(3) TO N
    IF a(i) < middle THEN v(y)=a(i): y=y+1: ELSE v(N-z)=a(i): z=z+1
NEXT
FOR k=q(3) TO q(3)+10: PRINT v(k);: NEXT: PRINT: FOR k=N-9 TO N: PRINT v(k);: NEXT: PRINT: PRINT
q(4)=y-1: q(1)=2: q(5)=N

' SORTING
PRINT "1="; 1, "2="; q(2), "3="; q(3), "4="; q(4), "5="; N: PRINT
FOR t=1 TO 4
    FOR i=q(t)-1 TO q(t+1): FOR j=i+1 TO q(t+1)
            IF v(i) > v(j) THEN SWAP v(i), v(j): s=s+1
NEXT: NEXT: NEXT

finish=TIMER

FOR k=1 TO 10: PRINT v(k);: NEXT: PRINT: FOR k=N-9 TO N: PRINT v(k);: NEXT: PRINT: PRINT
PRINT "DA RUS 4 ", finish-start; "second ", "swap "; s

OPEN "c:/RUsortdav4.txt" FOR OUTPUT AS #2
PRINT #2, finish-start; "second ", "swap "; s
PRINT #2, N; "Russian sorting halves 4 parts bubble "
FOR i=1 TO 20: PRINT #2, v(i): NEXT
FOR i=N-19 TO N: PRINT #2, v(i): NEXT

start=TIMER: s=0
FOR i=1 TO N: FOR j=i+1 TO N
        IF d(i) > d(j) THEN SWAP d(i), d(j): s=s+1
NEXT: NEXT
finish=TIMER

PRINT "BUBBLE ", finish-start; "second ", "swap "; s
END

РЕКУРСИЯ RECURSIVE


' Russian Sorting Halves Danilin

DECLARE SUB RussianSortingHalvesDAV (ab!, yz!, part!, age!)
CLOSE
OPEN "c:/N.txt" FOR INPUT AS #5
INPUT #5, n: PRINT n

'n=123456

age=1+LOG(n)/LOG(2)
PRINT n, age

DIM SHARED d(n) 'AS LONG
DIM SHARED a(n) 'AS LONG

'OPEN "c:/ISX.txt" FOR INPUT AS #1
'FOR i=1 TO n: INPUT #1, d(i): NEXT

FOR i=1 TO n: d(i)=n-i+1: NEXT ' INT(RND*n)
'FOR i=1 TO n STEP 2: d(i)=n-i+1: d(i+1)=d(i): NEXT
'FOR i=1 TO n: d(i)=INT(RND*n): NEXT '

IF n < 17 THEN FOR k=1 TO n: PRINT d(k);: NEXT: PRINT
IF n > 16 THEN FOR k=n-8 TO n: PRINT d(k);: NEXT: PRINT

start=TIMER

IF age > 0 THEN
 CALL RussianSortingHalvesDAV(1, n, 1, age)
END IF

finish=TIMER

IF n < 17 THEN FOR k=1 TO n: PRINT d(k);: NEXT: PRINT
IF n > 16 THEN FOR k=n-8 TO n: PRINT d(k);: NEXT: PRINT

PRINT finish-start

OPEN "c:/=RuSortHalves_dav.txt" FOR OUTPUT AS #2
PRINT #2, finish-start; "sekund "
PRINT #2, n; "elements", "RECURSION"
FOR i=1 TO 22: PRINT #2, d(i): NEXT
FOR i=n-22 TO n: PRINT #2, d(i): NEXT

FOR k=1 TO 20: PRINT d(k);: NEXT: PRINT: PRINT
FOR k=n-9 TO n: PRINT d(k);: NEXT: PRINT: PRINT

END

SUB RussianSortingHalvesDAV (ab, yz, part, age)

IF yz-ab < 1 THEN EXIT SUB

FOR i=ab TO yz
 summa=summa+d(i)
NEXT
middle=summa/(yz-ab+1)

abc=ab-1
xyz=yz+1

FOR i=ab TO yz
 IF d(i) < middle THEN abc=abc+1: a(abc)=d(i): ELSE xyz=xyz-1: a(xyz)=d(i)
NEXT

FOR i=ab TO yz: d(i)=a(i): NEXT

IF part < age THEN
 IF abc >= ab THEN CALL RussianSortingHalvesDAV(ab, abc, part+1, age)
 IF xyz <= yz THEN CALL RussianSortingHalvesDAV(xyz, yz, part+1, age)
END IF

END SUB


PureBasic Русская Сортировка Половинами и скорая и человеческая
PureBasic Russian Sorting Halves and fast and human

считывает только количество из c:/N.txt
удобно чтобы обходиться без оболочки PureBasic
и сортировав хоть миллиарды пишет по 1000
наименьших и наибольших в c:/RSH_DAV.txt

PureBasic Russian Sorting Halves Recursive
сортирует 1000000 за 0,3 секунды

; Russian Sorting Halves Danilin
OpenConsole()
Declare RussianSortingHalvesDAV (ab, yz, part, age)

;n=12345678

If ReadFile(0, "c:/N.txt")
 n=Val(ReadString(0))
 CloseFile(0)
EndIf

age=Int(1+(Log(n)/Log(2)))
Global Dim d(n)
Global Dim a(n)

For i=1 To n
 ;d(i)=Random(n,1) ; случайные значения от 1 до n
 d(i)=n-i+1;
Next

 ; вывод исходных значений до сортировки
PrintN(" Исходный без сортировки Первые 20")
For k=1 To 20: Print(" "+ d(k)): Next: PrintN("")
PrintN(" Последние 10")
For k=n-9 To n : Print(" "+ d(k)): Next: PrintN("")

start=ElapsedMilliseconds() ; таймер

If age > 0 :
 RussianSortingHalvesDAV(1, n, 1, age)
EndIf

finish=ElapsedMilliseconds() ; таймер

PrintN("RussianSorting Первые 50")
For k=1 To 50: Print(" "+ d(k)): Next: PrintN("")
PrintN(" Последние 20")
For k=n-19 To n : Print(" "+ d(k)): Next: PrintN("")

PrintN( "Время сортровки RussianSorting=" + Str(finish-start))

If OpenFile(0, "c:/RSH_DAV.txt")
 For k=1 To 1000 :WriteString (0, " " +d(k)): Next
 For k=n-1001 To n :WriteString (0, " " +d(k)): Next
 CloseFile(0)
EndIf

Input()
End

; Процедура сортировки
Procedure RussianSortingHalvesDAV (ab, yz, part, age)

If yz-ab < 1 :ProcedureReturn 0
EndIf

For i=ab To yz
summa=summa+d(i)
Next
middle=summa/(yz-ab+1)

abc=ab-1
xyz=yz+1

For j=ab To yz
If d(j) <= middle:
abc=abc+1: a(abc)=d(j)
Else
xyz=xyz-1: a(xyz)=d(j)
EndIf

Next

For w=ab To yz: d(w)=a(w): Next

If part < age :
If abc >= ab :RussianSortingHalvesDAV(ab, abc, part+1, age)
EndIf
If xyz < yz :RussianSortingHalvesDAV(xyz, yz, part+1, age)
EndIf
EndIf

EndProcedure



Russian sorting halves C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
namespace davApp
{
    class Program
    {
        private long age;
        static long[] a;
        static long[] d;

        static void Main(string[] args)
        {
            int n = 0;
            // read N from file
            var inpFile = new StreamReader("N.txt");
            n = Convert.ToInt32(inpFile.ReadLine());
            inpFile.Close();

            var age = 1 + Math.Log(n) / Math.Log(2);

            Console.WriteLine(n);

            a = new long[n + 1];
            d = new long[n + 1];

            // random in diapazon [1;n]
            var rand = new Random();
            for (int i = 1; i <= n; i++)
                d[i] = rand.Next(1, n);

            // read n line from file
            //for (int i = 1; i <= n; i++)
            //    d[i] = n - i + 1;

            //inpFile = new StreamReader("ISX.txt");
            //for (int i = 1; i <= n; i++)
            //    d[i] = Convert.ToInt64(inpFile.ReadLine());
            //inpFile.Close();

            // write on screen
            int m = Math.Min(n, 20);
            for (int i = 1; i <= m; i++)
                Console.Write("{0} ", d[i]);
            Console.WriteLine();

            // russian sorting halves
            var start = DateTime.Now;
            if (age > 0)
                dav(1, n, 1, age);
            var finish = DateTime.Now;

            Console.WriteLine("{0} second", (finish - start).TotalSeconds);

            // write on screen
            Console.WriteLine("[1..{0}]", m);
            for (int i = 1; i <= m; i++)
                Console.Write("{0} ", d[i]);
            Console.WriteLine();

            // write on screen
            Console.WriteLine("[{0}..{1}]", n - m + 1, n);
            for (int i = n - m + 1; i <= n; i++)
                Console.Write("{0} ", d[i]);
            Console.WriteLine();

            // write in file
            var outFile = new StreamWriter("dav.txt");
            for (int i = 1; i <= m; i++)
                outFile.WriteLine(d[i]);
            outFile.WriteLine();

            for (int i = n - m + 1; i <= n; i++)
                outFile.WriteLine(d[i]);
            outFile.WriteLine();
            outFile.Close();

            Console.WriteLine("Press any key");
            Console.ReadKey();

        }

        static void dav(int ab, int yz, int part, ****** age)
        {
            if (yz - ab < 1)
                return;

            long summa = 0;
            for (int i = ab; i <= yz; i++)
                summa = summa + d[i];

            ****** middle = summa / (yz - ab + 1);

            var abc = ab - 1;
            var xyz = yz + 1;

            for (int i = ab; i <= yz; i++)
                if (d[i] < middle)
                {
                    abc = abc + 1;
                    a[abc] = d[i];
                }
                else
                {
                    xyz = xyz - 1;
                    a[xyz] = d[i];
                }

            for (int i = ab; i <= yz; i++)
                d[i] = a[i];

            if (part < age)
            {
                if (abc >= ab) dav(ab, abc, part + 1, age);
                if (xyz <= yz) dav(xyz, yz, part + 1, age);
            }
            return;
        }
    }
}




Результат экспериментов для предыдущего языка:
копия массива результатов в данные только целиком ухудшает
и больше преуспеют языки где есть быстрый подсчёт суммы
и копирование части массива результатов в массив данных

Русская Сортировка Третями
распределяющая: меньше трети и больше двух третей
выглядит бесконечно при рекурсии
ведь непонятно как переходить между третями

Зато делить массив на 3/9/27 частей очевидно легко
в то время как Русская сортировка половинами делит
массив на 2/4/8 частей как Русская Сортировка Осьмушками