Копипаст

Копипаст | Русская сортировка половинами: человеческая сортировка быстрее в 4 раза и МЫ

Данная статья только для индексации
чтобы другие сайты не присвоили авторство
и в комментариях ссылки на сборники алгоритмов и визуализаций
и ещё проверяется всевозможное форматирование
и включает таблицы из ucoz

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

Цель: заинтересовать народ созданием программы
Русская сортировка половинами
на других любых языках программирования

Особенность программы «Русская сортировка половинами»:
уникальная картина сортировки и ускорение алгоритмов сортировки.



Допустим требуется сортировать массив N=11 чисел

Массив d(1,1...N)

2 8 1 6 7 10 4 11 9 3 5

Среднее значение: 6 как сумма данных ячеек делить на число ячеек

2 8 1 6 7 10 4 11 9 3 5   Исходный массив d(1,1...N)
                        Предыдущих ячеек: 0
2                       2 < 6 в начало счётчик = 1
2                   8   8 >= 6 в конец счётчик = 1
2 1                 8   1 < 6 в начало счётчик = 2
2 1               6 8   6 >= 6 в конец счётчик = 2
2 1             7 6 8   7 >= 6 в конец счётчик = 2
2 1           10 7 6 8   10 >= 6 в конец счётчик = 2
2 1 4         10 7 6 8   4 < 6 в начало счётчик = 3
2 1 4       11 10 7 6 8   11>= 6 в конец счётчик = 3
2 1 4     9 11 10 7 6 8   9 >= 6 в конец счётчик = 3
2 1 4 3   9 11 10 7 6 8   3 < 6 в начало счётчик = 4
2 1 4 3 5 9 11 10 7 6 8   5 < 6 в начало счётчик = 5

Массив d(2,1...N) и счётчик = 5

2 1 4 3 5 9 11 10 7 6 8

Любая из левых 5 ячеек меньше, чем любая из правых 6 ячеек.

Массив d(2,1...N) условно делится на 2 части:

2 1 4 3 5   и   9 11 10 7 6 8

и ячейки проходят ещё циклы независимо друг от друга,
сохраняя непрерывность массива d(2,1...N).

Сравнение формул для оценки максимального ускорения других сортировок

русская
сортировка
2 части
смены =x*(N/x)*((N/x)-1)/2 N=8 x=2 =2*4*3/2 12 N=100 2450
пузырьковая bubble смены =N*(N-1)/2 N=8 =8*7/2 28 N=100 4950
русская
сортировка
4 части
смены =x*(N/x)*((N/x)-1)/2 N=8 x=4 =4*2*1/2 4 N=100 1200

Русская сортировка половинами: человеческая сортировка быстрее в 4 раза и МЫРусская сортировка половинами: человеческая сортировка быстрее в 4 раза и МЫРусская сортировка половинами: человеческая сортировка быстрее в 4 раза и МЫ
100ооо шт.   

русская сортировка 4 части 70 секунд
русская сортировка 2 части 170 секунд
пузырьковая bubble 230 секунд
выбором select 140 секунд
русская сортировка выбором 2 части 105 секунд
русская сортировка выбором 4 части 67 секунд


текстовые строки

русская сортировка 2 части 1000 строк циклы 264280 смен 137131
пузырьковая bubble 1000 строк циклы 499500 смены 264139
русская сортировка 2 части 100ооо строк 390 секунд
пузырьковая bubble 100ооо строк 650 секунд


быстрее чем:  faster than:

selection insertion binary bubble cocktail
gnome comb heap smooth odd-even
bitonic cyrcle blockmerge    


медленнее чем: slower than:

merge quick shell radix tim


 
Русская сортировка половинами требует данные:
c:/N.txt = только количество элементов и
c:/ISX.txt = элементы в столбец в требующемся количестве возможно создать в excel
=случмежду(1000;100000)
и скопировав вставить текст в c:/ISX.txt

'RUSSIAN sort halves
OPEN "c:/N.txt" FOR INPUT AS #5
INPUT #5, n
DIM d(3, n), sum(3, 4), sred(3, 4), y(3, 2),q(5)

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

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

start=TIMER: p=0: s=0
m=1: q=1

' 1-u PROXOD
FOR i=1 TO n: sum(m,q)=sum(m,q)+d(m,i): NEXT
sred(m,q)=sum(m,q) / n

y(m,q)=1: z=0: FOR i=1 TO n
    IF d(m,i) < sred(m,q) THEN d(m+1, y(m,q))=d(m,i): y(m,q)=y(m,q)+1: ELSE d(m+1, n-z)=d(m,i): z=z+1
NEXT

y(m,q)=y(m,q)-1
m=m+1: q=q * 2

FOR i=1 TO n: sum(m,1)=sum(m,1)+d(m,i): NEXT
sred(m,1)=sum(m,1) / n

IF n < 17 THEN FOR k=1 TO n: PRINT d(m,k);: NEXT: PRINT: PRINT y(m-1,1), sred(m-1,1): PRINT
IF n > 16 THEN FOR k=n-10 TO n: PRINT d(m,k);: NEXT: PRINT: PRINT y(m-1,1), sred(m-1,1): PRINT

' BKL NOMER MENSHE SRED 1
' KONEZ 1-GO

'DELIM 1-e  iz 2-x

sum(m,q-1)=0

FOR i=1 TO y(m-1,q-1): sum(m,q-1)=sum(m,q-1)+d(m,i): NEXT
sred(m,q-1)=sum(m,q-1) / (y(m-1,q-1))

y(m,q-1)=1: z=0

FOR i=1 TO y(m-1,q-1)
    IF d(m,i) < sred(m,q-1) THEN: d(m+1, y(m,q-1))=d(m,i): y(m,q-1)=y(m,q-1)+1 ELSE d(m+1, y(m-1,q-1)-z)=d(m,i): z=z+1
    IF n < 17 THEN FOR k=1 TO y(m-1,q-1): PRINT d(m,k);: NEXT: PRINT "*";: FOR k=1 TO y(m-1,q-1): PRINT d(m+1, k);: NEXT: PRINT
NEXT

'DELIM 2-e  iz 2-x

sum(m,q)=0
FOR i=y(m-1,q-1)+1 TO n: sum(m,q)=sum(m,q)+d(m,i): NEXT:
sred(m,q)=sum(m,q) / (n-y(m-1,q-1)):
PRINT: PRINT sum(m,q), sred(m,q), (n-y(m-1,q-1)),

'DALEE

y(m,q)=y(m-1,q-1)+1: z=0
PRINT "ot"; y(m-1,q-1)+1; "do "; n

FOR i=y(m-1,q-1)+1 TO n
    IF d(m,i) < sred(m,q) THEN d(m+1, y(m,q))=d(m,i): y(m,q)=y(m,q)+1 ELSE d(m+1, n-z)=d(m,i): z=z+1
    IF n < 17 THEN FOR k=y(m-1,q-1)+1 TO n: PRINT d(m,k);: NEXT: PRINT "=";: FOR k=y(m-1,q-1)+1 TO n: PRINT d(m+1, k);: NEXT: PRINT
NEXT

y(m,q)=y(m,q)-1

' SORTIROVKA
'to4ki kontrol 1 21 11 22 n

q(1)=2
q(2)=y(m,q-1) '2 1
q(3)=y(m-1,q-1) '1 1
q(4)=y(m,q) '2 2
q(5)=n

PRINT m
PRINT "2="; q(2); m; q-1,
PRINT "3="; q(3); m-1; q-1,
PRINT "4="; q(4); m; q
PRINT

m=m+1

FOR t=1 TO 4
    FOR i=q(t)-1 TO q(t+1): FOR j=i+1 TO q(t+1)
            IF d(m,i) > d(m,j) THEN SWAP d(m,i), d(m,j): p=p+1
        s=s+1: NEXT: 'FOR k=1 TO n: PRINT d(m,k);: NEXT: PRINT: PRINT m
    NEXT
NEXT

finish=TIMER

IF n < 17 THEN FOR k=1 TO n: PRINT d(m,k);: NEXT: PRINT: PRINT y(m-1, 1), sred(m-1, 1): PRINT
IF n > 16 THEN FOR k=n-10 TO n: PRINT d(m,k);: NEXT: PRINT: PRINT y(m-1, 1), sred(m-1, 1): PRINT
'FOR k=1 TO n: PRINT d(m,k);: NEXT: PRINT
PRINT finish-start, s, p

OPEN "c:/=sortda444bubble.txt" FOR OUTPUT AS #2
PRINT #2, finish-start; "секунд ", "циклы "; s, "смены "; p
PRINT #2, n; "шт.", "русская сортировка 4 части цикл массив"
FOR i=1 TO n: PRINT #2, d(m,i): NEXT
END

Цель: заинтересовать народ созданием программы
Русская сортировка половинами
на других любых языках программирования

Нобелевская премия сама себя не получит
Nobel Prize will not receive itself
Le prix Nobel ne se recevra pas
★3
Сортировка Таноса :: Thanos sort
algolab.valemak.com/thanos
включает рецензию и классификацию сортировки темы

главное: сортировка…? чего?
средне-арифметическая корзинная сортировка распределением интегралов
и именно для интегралов физических и абстрактных
вижу наибольшую пользу:
сортировка грузов или пути или других интегралов

и ведёт в сборник 60 сортировок
algolab.valemak.com/
8 сервисов визуализации в т.ч. сортировок
tproger.ru/digest/8-algorithm-visualizers/
сортировки на сотне языков программирования
rosettacode.org/wiki/Category:Sorting_Algorithms
и возможно выйти на другие алгоритмы
и например группировать по интересующему языку
Вы на первом шаге считаете сумму чисел в массиве, а это сразу как минимум O(n) так что данный алгоритм в лучшем случае может составить конкуренцию так называемым квадратичным алгоритмам, но те в свое время имеют известные особенности будь-то получение первого сортированного элемента за один проход как селекшен сорт или же работа с постоянно пополняющимся массивом как при инсершен сорт.
avatar
значит всё поняли правильно

и посмотрите подтверждение есть в статье:
«быстрее чем» и «медленнее чем»

и если визуализировать сортировку пузырьковую
как пирамиду перестановок N*(N-1)/2
то моя идея добавляет 2 полоски арифметически
и делит массив половинами геометрически

и чем больше массив
тем влияние добавления операций меньше
в интернете управляемая визуализация сортировок
https://airtucha.github.io/SortVis/
лучше выбирать число столбцов 25 поменьше
https://toptal.com/developers/sorting-algorithms/
http://sorting.at
а также самостоятельно изучайте всевозможные сортировки в википедиях
о чём речь про защиту от присвоения авторства:

сайт блогов HABR отказывается публиковать данную статью
ссылаясь мол опубликовано мной на моём сайте в 2014 году

тогда им же хуже и парадоксально:

данная тема развивается на дюжине форумов
повсюду… кроме… сайта блогов программистов

поэтому мы так и живём
в смысле поэтому мы так и существуем
В трейдинге лучше вообще отказаться и от сортировок и от поиска. Если речь про быстрые алго
avatar
копия данной темы развивается на дюжине форумов
и на каждом форуме найдётся свой… интеграл

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

налево малые коэффициенты и ставки крупные
направо крупные коэффициенты и ставки малые

что приводит к результатам вида +250 -50

Интеграл Логарифмович, 
и на каждом форуме найдётся свой… интеграл 
ну удачи вам развить тут тему.
avatar
надо додумать как использовать против кредитов
и против процентов по кредитам

ведь ускоренная выплата кредитов экономя 30%

та же сортировка: то что теряли типа вниз
то же направляется в развитие типа вверх

между графиками парабола и прямая:
треугольник был пассив
треугольник стал актив

на сегодня программа реализована на 2-х языках
и вижу перспективы: олимпиады по информатике
ведь помню я и сам участвовал и побеждал
Русская Сортировка Половинами Визуально Данилин
Russian Sort Halves Visual Danilin

советовали обратиться на форум dxdy
и я для начала накануне создал тему
«Ищу youtube про Интеграл с натуральными осями вместо Х и У»

поступил простой встречный вопрос
и я ответил процитировав название темы

потом тему перенесли в карантин из тем
казалось бы свободного общения форума dxdy

и с целью исправления внёс 1 анимацию и 1 ютюб
причём ютюб никак не переводится в телевизор

ночью пришёл ответ:

«Ну, стало быть, уже нашли,
дальнейший поиск не требуется. Тема удалена»

… вот поэтому мы все так и существуем…

p.$. и заодно доказано: что пишу все понимают со 2-го раза
Русская Сортировка Половинами Ускоряет Данилин
Russian Sort Halves Accelerate Danilin


Русская сортировка половинами быстрее Данилин
Russian Sort Halves faster Danilin
 


остающиеся 2 элемента удобно сортировать
ища через «если» из 2 вариантов аб ба
и 3 элемента сортировать ища через «если»
из 6 вариантов абв авб бав бва вба ваб





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


Русская сортировка половинами все действия
За минувшее лето разобрана программа единомышленника
и создана улучшенная QB64 Qbasic рекурсивная
Русская сортировка половинами Russian Sorting Halves

показывающая результаты:
там где пузырьковая сортирует 100'ооо за 230 секунд
там где пузырьковая половинами 100'ооо за 70 секунд

там Рекурсия Русская сортировка половинами за 0,33 секунды
и миллион сортирует за 2,2 секунды именно в QB64 Qbasic
повторяю: 1'000'ooo сортирует за 2,2 секунды в QB64 Qbasic

и приветствую версии на других языках программирования
особенно где возможна визуализация и сравнение сортировок

4-кратное ускорение
a 4 times acceleration proof

'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
RussianSortingHalvesDAV.bas: рекурсия QB64 Qbasic QuickBasic Basic рекурсия

ускоряющее развитие:
вместо 2-мерного массива 2 массива d(N) и a(N)
и действительно успешно: сортирует 100ооо за 0,22 секунды

сортирует 1000ооо за 2,2 секунды
сортирует миллион за 2,2 секунды
sorts 1'000'000 in 2.2 seconds
сортирует 1'000'000 за 2,2 секунды

' 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
Результат экспериментов для предыдущего языка:
копия массива результатов в данные только целиком ухудшает
и больше преуспеют языки где есть быстрый подсчёт суммы
и копирование части массива результатов в массив данных

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

Зато делить массив на 3/9/27 частей очевидно легко
в то время как Русская сортировка половинами делит
массив на 2/4/8 частей как Русская Сортировка Осьмушками
Russian Sorting Halves and fast and human
sorts 1'000'000 in 0.2 seconds on C# Csharp

Код:
<code>
// RUSSIAN SORTING HALVES DANILIN
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 NUMBERS
            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];

            for (int i = 1; i <= n; i++)
                d[i] = n - i + 1;

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

            // REAN N LINE FROM FILE
            //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 DANILIN
            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, double age)
        {
            if (yz - ab < 1)
                return;

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

            double middle = summa / (yz - ab + 1.0);

            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;
        }
    }
}
</code>
Russian Sorting Halves and fast and human
sorts 1'000'000 in 2.2 seconds on QB64
sorts 1'000'000 in 0.3 seconds on PureBasic
sorts 1'000'000 in 0.2 seconds on C# Csharp
разделение пузырьковой сортировки на 4 части
ускоряет в 4 раза и данный пример C# и выше qb64
чудесные примеры для обучения включающие важное



Z = N*(N-1)/2
Z = 4*(N/4*(N/4-1)/2+2*N/4)
Z = log(N;2)*(N/log(N;2)*(N/log(N;2)-1)/2+2*N/log(N;2))

// Russian Sorting Halves 4 part accelerate bubble sorting
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace octoberApp
{
 class Program
 {
 static int n;
 static double[] d;
 static double[] a;
 static double[] v;
 static int[] q;

 static void Main(string[] args)
 {
 n = 37519;

 d = new double[n+1];
 a = new double[n+1];
 v = new double[n+1];
 q = new int[5+1];
 var rand = new Random();
 for (int i = 1; i <= n; i++)
 d[i] = Math.Truncate(rand.NextDouble() * n);

 for (int i = 1; i <= 10; i++)
 Console.Write("{0} ", d[i]);
 Console.WriteLine();

 for (int i = n — 9; i <= n; i++)
 Console.Write("{0} ", d[i]);
 Console.WriteLine();
 Console.WriteLine();

 var start = DateTime.Now;
 var s = 0;
 //ALL
 double summa = 0;
 for (int i = 1; i <= n; i++)
 summa += d[i];
 double middle = summa / n;
 var y = 1;
 var z = 0;

 for (int i = 1; i <= n; i++)
 if (d[i] < middle)
 {
 a[y] = d[i]; y++;
 }
 else
 {
 a[n — z] = d[i];
 z++;
 }

 q[3] = y — 1;
 Console.WriteLine(«ALL middle = {0}», middle);

 for (int i = 1; i <= 10; i++)
 Console.Write("{0} ", a[i]);
 Console.WriteLine();
 for (int i = n — 9; i <= n; i++)
 Console.Write("{0} ", a[i]);
 Console.WriteLine();
 Console.WriteLine();

 // 1 FROM 2
 summa = 0;
 for (int i = 1; i <= q[3]; i++)
 summa += a[i];

 middle = summa / q[3];
 y = 1;
 z = 0;
 Console.WriteLine(«1 FROM 2 = {0} 1 ...{1}», middle, q[3]);

 for (int i = 1; i <= q[3]; i++)
 if (a[i] < middle)
 {
 v[y] = a[i]; y++;
 }
 else
 {
 v[q[3] — z] = a[i];
 z++;
 }

 for (int i = 1; i <= 10; i++)
 Console.Write("{0} ", v[i]);
 Console.WriteLine();
 for (int i = q[3] — 9; i <= q[3]; i++)
 Console.Write("{0} ", v[i]);
 Console.WriteLine();
 Console.WriteLine();

 q[2] = y — 1;

 // 2 FROM 2
 summa = 0;
 for (int i = q[3] + 1; i <= n; i++)
 summa += a[i];
 middle = summa / (1 + n — q[3]);
 y = q[3];
 z = 0;
 Console.WriteLine(«2 FROM 2 = {0} {1}...{2}», middle, q[3] + 1, n);
 for (int i = q[3]; i <= n; i++)
 if (a[i] < middle)
 {
 v[y] = a[i]; y++;
 }
 else
 {
 v[n — z] = a[i];
 z++;
 }
 for (int i = q[3]; i <= q[3] + 10; i++)
 Console.Write("{0} ", v[i]);
 Console.WriteLine();
 for (int i = n — 9; i <= n; i++)
 Console.Write("{0} ", v[i]);
 Console.WriteLine();
 Console.WriteLine();

 q[4] = y — 1;
 q[1] = 2;
 q[5] = n;

 //BUBBLE
 Console.WriteLine(«1= {0} 2= {1} 3= {2} 4= {3} 5= {4}», 1, q[2], q[3], q[4], n);
 Console.WriteLine();

 for (int t = 1; t <= 4; t++)
 for (int i = q[t] — 1; i <= q[t + 1]; i++)
 for (int j = i + 1; j <= q[t + 1]; j++)
 if (v[i] > v[j])
 {
 var x = v[i];
 v[i] = v[j];
 v[j] = x;
 s++;
 }

 var finish = DateTime.Now;

 for (int i = 1; i <= 10; i++)
 Console.Write("{0} ", v[i]);
 Console.WriteLine();

 for (int i = n — 9; i <= n; i++)
 Console.Write("{0} ", v[i]);
 Console.WriteLine();
 Console.WriteLine();
 Console.WriteLine(«DArus4 {0} second swap {1}», (finish — start).TotalSeconds, s);

 start = DateTime.Now;
 s = 0;

 for (int i = 1; i <= n; i++)
 for (int j = i + 1; j <= n; j++)
 if (d[i] > d[j])
 {
 var x = d[i];
 d[i] = d[j];
 d[j] = x;
 s++;
 }
 finish = DateTime.Now;

 Console.WriteLine(«BUBBLE {0} second swap {1}», (finish — start).TotalSeconds, s);

 Console.WriteLine(«Press any key»);
 Console.ReadKey();
 }
 }
}

Исследуя логарифм получается:
формула включающая логарифм вытекает из расчёта
вероятности угадать подряд события равновероятные

Например простейшее: 0,7*0,7*0,7 = 0,7^3 = 0,343
в какую степень надо возвести 0,7 чтобы получить 0,343
и в 20-м веке формулу восстановил Андрей Данилин
N = LOG(0,343)/LOG(0,7) = 3
и соответствующая формула для неугадывания

Умножение постоянных вероятностей C+р^N=1
и в 20-м веке формулу восстановил Андрей Данилин
N = LOG(1-C)/LOG(1-p)
С — вероятность выигрыша гарантированного
р — вероятность выигрыша события.

Например задача: число несовпадений подряд
с вероятностью 99% для вероятности 48,65%
и в 20-м веке формулу восстановил Андрей Данилин
N = LOG(1-0,99)/LOG(1-0,4865) = 7
и значит на вероятности около 50%
легко неугадать 7 раз подряд

Упрощённо можно рассчитывать:
формулу открыл Андрей Данилин
N = 7+(5*(1/x-2))
например х=0,1 N=47 нормально и х=0,78 N=4 нормально.

Те же формулы справедливы и для вероятностей выше 50%.

Investigating logarithm is obtained:
formula including logarithms follows from calculation
probabilities of guessing consecutive events

For example, simplest: 0.7*0.7*0.7 = 0.7^3 = 0.343
in what degree it is necessary to build 0.7 to get 0.343
formula restored Andrey Danilin from Russia
N = LOG(0.343)/LOG(0.7) = 3
and corresponding formula for non-guessing

Multiplication of constant probabilities C+p^N=1
gives formula restored Andrey Danilin from Russia
N = LOG(1-C)/LOG(1-p)
C is probability of winning guaranteed
P is probability of winning an event.

For example, task: number of mismatches in a row
with a probability of 99% for probability of 48.65%
formula discovered Andrey Danilin from Russia
N = LOG(1-0,99)/LOG(1-0,4865) = 7
and therefore probability of about 50%
easy to guess 7 times in a row

Simplified can be calculated by
formula discovered Andrey Danilin from Russia
N = 7+(5*(1/x-2))
For example, x=0.1 N=47 is normal & x=0.78 N=4 is normal.

Same formulas are valid for probabilities above 50%.
Русская Сортировка Вероятностей
Русская Сортировка Интегралов

Russian Sorting of Probabilities
Russian Sorting of Integrals

теги блога Логарифм Интегралыч

....все тэги



UPDONW