Пятница, 29.03.2024, 16:50
Приветствую Вас Гость | RSS

 
 

Анти случайный математический сайт: всё Бесплатно 18+ kenokeno.ucoz.ru

Anti chaotically math site all FREE against losses против проигрышей 18+

 
Карта мира Пирамида Жизни Визуальная математика Всеобуч CoronaVirus

карта статистики посетителей & исследования и конкурсы бесплатные & ВКонтакте & Математический Блог & КеноКено & КЕНО ЮТЮБ KENO mini YOUTUBE

БЕЗ рекламы БЕЗ партнёрских БЕЗ рефералов NO advertising NO partners NO referrals pas de publicite pas de partenaires pas de references

Ссылки внутри страниц открываются в новой вкладке Links inside pages open in a new tab of browser

КЕНО ЮТЮБ KENO mini YOUTUBE КЕНО ЮТЮБ KENO mini YOUTUBE КЕНО ЮТЮБ KENO mini YOUTUBE КЕНО ЮТЮБ KENO mini YOUTUBE КЕНО ЮТЮБ KENO mini YOUTUBE КЕНО ЮТЮБ KENO mini YOUTUBE КЕНО ЮТЮБ KENO mini YOUTUBE КЕНО ЮТЮБ KENO mini YOUTUBE КЕНО ЮТЮБ KENO mini YOUTUBE

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

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

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

ключевые 27

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

 

keywords 27

ours aliens others
active passive saving
leader slave victim
life machine language
target time control
service goods quality
export exploitation technology
integral logarithm derivative
elite antielite priority

 

 

Россия видит мир из будущего

Russia looks world from future

Rossiya vidit mir iz buduschego

IQ бесплатно Яндекс.Метрика

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

i always write only about myself and anything to anyone never recommend

мен әрқашан тек өзіме жазамын және ешқашан ешкімге ештеңе ұсынбаймын

завжди пишу тільки про себе і ніколи нікому нічого не рекомендую

web.archive.org/web/20230602154543///kenokeno.ucoz.ru/publ/

ich schreibe immer nur über mich selbst und empfehle niemandem etwas

j'écris toujours seulement sur moi-même et je ne recommande

mi ĉiam skribas nur pri mi mem kaj neniam rekomendas ion al iu

siempre escribo solo para mí y nunca recomiendo nada a nadie

web.archive.org/web/20230602152617///kenokeno.ucoz.ru/load/

 

Главная | Регистрация | Вход

 
Главная » Файлы » Мои файлы

Русская Сортировка Половинами и quicksort быстрая сортировка qbasic и МЫ
[ Скачать с сервера (4.50 Mb) ] 16.04.2014, 18:41

Русская Сортировка Половинами и quicksort быстрая сортировка qbasic и МЫ

Русская Сортировка Половинами Данилин Russian Sorting Halves Danilin visualization

Русская Сортировка Половинами Данилин Russian Sorting Halves Danilin visualisation

летом 2018 года получено Свидетельство:
Русская сортировка половинами

на изображении часть свидетельства
без герба и без номеров и без ФИО


Русская Сортировка Половинами Данилин Russian Sorting Halves Danilin visualisation

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 Danilin visualisation

Russian sorting halves important actions visualisation

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

суммируя массив номеров букв
и разделив на количество элементов

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

и ускорение человеческой сортировки
думаю ускорит путь и время
Русская Сортировка Половинами Данилин Russian Sorting Halves Danilin visualization

сортировка олицетворяется в виде:
перемещается масса на расстояние

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

работа как сумма произведений
массы груза на перемещения = работа

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

там моя Русская сортировка половинами
требует интеграл работы 12 значит
Русская сОртирОвка пОлОвинами лучше
 

На тему сортировка читая дюжину статей
с программами иногда часто вижу ляп:

для А элементов 2 вложенных массива
равные и число перестановок якобы А^2

зато правильнее: I от1 доА и J отI доА
и видимо те ошиблись пиша 1 вместо I
причём часто противореча пояснениям

для А=100 требуется А^2=10ооо ходов
а правильнее =100*(99)/2 =4950 ходов
2-жды меньше видно из формулы

и ещё вникнув в сортировку пополам
получается для А=100
=2*((100/2)*((100/2)-1)/2) = 2450 ходов
4-жды меньше чем советуют по интернету
и возможно реально делить на 4 части и
далее сортируется пузырьковая сортировка

Проведя эксперимент контролируя время
сортируя массив обратный от 100ооо до 1

qbasic: пополам 135 секунд и А^2 215 секунд
простой 389 секунд и А^2 497 секунд
чужие непонятные около 200 секунд

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

В свете вышесказанного: на тему сортировка и МЫ
обнаруживаются остроумные решения
ускоряющие тысячи операций в разы

Вдобавок создал строки контролирующие время
и возможно проверять на скорость варианты сортировки

Рекурсия доступна в вариантах Excel & QB64 Qbasic & C#

Русская Сортировка Половинами Данилин Russian Sorting Halves Danilin visualization

вкратце: рассчитываем средний элемент
и за 1 цикл раскидываем в начало и в конец
в другой массив и сортируем 2 части неравные раздельно

1-вые циклы лишь заполнение массива
специально худшими значениями и заодно
100ооо элементов сортировал за менее 120 секунд
1ооо сортирует за 0,05с за 274ооо проходов и 4600 перестановок

любителям сортировать ютюб

додумав деление на 4 участка

100ооо элементов наизнанку сортировались 66 секунд

 

деля на 4 части перешёл от имён в 2-мерный массив

известна формула количества проходов
= LOG(N) / LOG(2)
для создания вложенных циклов

общие строки при правильном расположении
внутри программы рассчитывают время

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

n=100000
RANDOMIZE TIMER

FOR i=1 TO n
    a(i)=n-i+1
    'a(i)=INT(RND*n)
NEXT: PRINT: PRINT

start=TIMER: p=0: s=0

s=s+1 ' число циклов
p=p+1 ' число перестановок

finish=TIMER

FOR i=1 TO n: PRINT a(i);: NEXT

PRINT: PRINT: PRINT finish-start, s, p
END

оказывается худшими исходными данными
являются данные специально подготовленные
и подтверждается формула числа перестановок:
=2*4*3/2 = 12 перестановок и 6 перестановок

вместо изначальных =8*7/2 = 28 перестановок
и вместо массово ошибочного числа перестановок
=8^2 = 64 перестановок
12 перестановок в 5 раз быстрее
6 перестановок в 10 раз быстрее

Русская Сортировка Половинами Данилин Russian Sorting Halves Danilin visualization

в процессе соревнования сортировок
выявил 3 алгоритма basic и мой занимал 3-е место
отставая на доли секунды

и далее удалось оптимизировать как и предполагалось
в начале темы разделив массив пополам и ещё пополам

и посмотрев файл результатов всё отсортировано

10ооо ячеек за о,72 с а оппонент почти секунду
22ооо ячеек за 3,3 с а оппонент почти 5 сек
100ооо ячеек за 66 с а оппонент за 90 сек

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

Русская Сортировка Половинами Данилин Russian Sorting Halves Danilin visualization

Russian sorting halves all actions visualization

инструкция испытаний:
все программы содержат строки подключающие
одинаковый массив данных создаваемый управляемо
в виде 1/4-й разной мощности

в файле c:/N.txt указано количество и мощности
программа zapoln.exe формирует массив на c:/
сортировщики стартуя считывают одно и то же

и в процессе показывают одинаковые сообщения
и подсчитывают время чисто сортировки сообщая
на экране время и число проходов и перестановок
и сортировав пишут сортированное на c:/

Нобелевская премия сама себя не получит

Русская Сортировка Половинами Данилин Russian Sorting Halves Danilin visualization

реализовал подсчёт числа перестановок и проходов и создал
универсальные строки добавляемые в программы для сравнения

хоть bas хоть exe: конкурс сортировок и универсальная
оболочка: число ячеек n и признаки четвертей массива
abcd в файл c:/N.txt

zapoln.bas / ехе создаёт c:/ISX.txt с целью создать
области заполненные данными большими и малыми
и реально создавать любой массив
одинаковый для любого сортировщика

zapoln.bas

OPEN "c:/N.txt" FOR INPUT AS #5
INPUT #5, n, a, b, c, d

DIM d(n)

RANDOMIZE TIMER

FOR i=1 TO INT(n/4)
    d(i)=INT(RND*100*a)+a
    d(n/4+i)=INT(RND*100*b)+b
    d(n/2+i)=INT(RND*100*c)+c
    d(3*n/4+i)=INT(RND*100*d)+d
NEXT

OPEN "c:/ISX.txt" FOR OUTPUT AS #1

FOR i=1 TO n
PRINT #1, d(i): NEXT
END

встраиваем ключевые строки и тестируем и контролируем

OPEN "c:/N.txt" FOR INPUT AS #5
INPUT #5, n

DIM d(n)

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

FOR k=n-10 TO n: PRINT d(k);: NEXT: PRINT
start=TIMER: p=0: s=0

FOR i=1 TO n-1: FOR j=i TO n
        IF d(i) > d(j) THEN SWAP d(i), d(j): p=p+1
s=s+1: NEXT: NEXT

finish=TIMER

FOR i=n-10 TO n: PRINT d(i);: NEXT: PRINT
PRINT finish-start, s, p

OPEN "c:/REZ55.txt" FOR OUTPUT AS #2
FOR i=1 TO n: PRINT #2, d(i): NEXT
END

сортировка считывающая данные из c:/ISX.txt
и пишущая в ==sortda2yshz.txt

школьная сортировка и циклы и переменные

' DA 2 SIDE MASSIV sort
OPEN "c:/N.txt" FOR INPUT AS #5
INPUT #5, n

DIM d(2,n),q(3)

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

FOR k=n-10 TO n: PRINT d(1,k);: NEXT: PRINT
start=TIMER: p=0: s=0

FOR i=1 TO n: sum1=sum1+d(1,i): NEXT
sred1=sum1 / n: PRINT sred1: PRINT

y=1: z=0: FOR i=1 TO n
    IF d(1,i) < sred1 THEN d(2,y)=d(1,i): y=y+1: ELSE d(2,n-z)=d(1,i): z=z+1
    '    FOR k=1 TO n: PRINT d(2,k);: NEXT: PRINT
NEXT: PRINT

FOR i=1 TO n: sum2=sum2+d(2,i): NEXT
sred2=sum2 / n: PRINT sred2,y: PRINT

q(1)=1: q(2)=y-1: q(3)=n

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

finish=TIMER

FOR i=1 TO n: sum3=sum3+d(2,i): NEXT: sred3=sum3 / n: PRINT

FOR i=n-10 TO n: PRINT d(2,i);: NEXT: PRINT
PRINT finish-start, s, p

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

Пределы частей разделения массива избегают команду goto

Тестирование на одинаковых массивах

пузырьковая bubble = все со всеми: ошибочный массовый алгоритм из интернета
школьная = улучшенная пузырьковая: различные элементы без перестановки равных

русская сортировка: школьная или выбором включая деление на 2 части включает
цикл и переменные без индекса и улучшенная школьная и массив делится на 2 части
и также улучшается сортировка выбором и другие человеческие нормальные понятные
и возможно делить на 4 части

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

100ооо шт.   

русская сортировка 4 части 70 секунд
русская сортировка 2 части 170 секунд
школьная 230 секунд
пузырьковая bubble 440 секунд
выбором сортировка select 140 секунд
русская сортировка выбором 2 части 105 секунд
русская сортировка выбором 4 части 67 секунд
Русская Сортировка Половинами
Рекурсия Qbasic QB64 100'ооо
0,22 секунд
Русская Сортировка Половинами
Рекурсия Qbasic QB64 1'000'ооо
2,5 секунд
Русская Сортировка Половинами
Рекурсия PureBasic 1'000'ооо
0,3 секунд
Русская Сортировка Половинами
Рекурсия C# 1'000'ооо
0,2 секунд
Русская Сортировка Половинами
Рекурсия FreeBasic 1'000'ооо
0,15 секунд

1000 шт.  

русская сортировка 4 части циклы  135048 смены  39725
русская сортировка 2 части циклы   261342 смены   92805
школьная циклы   499500  смены   227585
пузырьковая bubble internet ошибочная циклы   998001 смены   227585
выбором сортировка select циклы      999 смены      6346
русская сортировка выбором 2 части циклы      999 смены     4406
русская сортировка выбором 4 части циклы      999 смены    3811

Русская Сортировка Половинами Данилин Russian Sorting Halves Danilin visualization

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

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

growingwiththeweb.com/projects/sorting-visualiser/

algolab.valemak.com/thanos
algolab.valemak.com/
algolab.valemak.com/links

а также самостоятельно изучайте всевозможные сортировки в википедиях

shell сортировка

' SHELL сортировка

n = 100000
DIM a(n)

FOR i = 1 TO n: a(i) = INT((RND * 1000) + 5): NEXT
FOR k = n - 10 TO n: PRINT a(k);: NEXT: PRINT
start = TIMER

' algorithm

d = n \ 2
WHILE d > 0
 DO
 done = 1
 FOR i = 1 TO n - d
 IF a(i) > a(i + d) THEN
 SWAP a(i), a(i + d)
 done = 0
 END IF
 NEXT
 LOOP UNTIL done
 d = d \ 2
WEND

' algorithm

finish = TIMER
FOR i = n - 10 TO n: PRINT a(i);: NEXT: PRINT
PRINT finish - start
END

select сортировка выбором сравнивает текущий
с максимальным из оставшихся и переставляет местами

FOR i = 1 TO n - 1
    min = i
    FOR j = i + 1 TO n
        IF d(min) > d(j) THEN min = j
    NEXT j
    SWAP d(i), d(min)
NEXT i


самым быстрым Qbasic совместимым пока считаю

неизвестно где найденный алгоритм QuickSort Qsort
дополненный моими счётчиками

OPEN "c:/N.txt" FOR INPUT AS #5
INPUT #5, n

DIM x(n) AS LONG
DIM y(-1 TO n) AS LONG
y(-1) = 1

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

FOR k = n - 10 TO n: PRINT x(k);: NEXT: PRINT
start = TIMER: p = 0: s = 0

' algorithm

FOR i = 1 TO n
    y(x(i)) = y(x(i)) + 1: p = p + 1
NEXT i
 
FOR i = 1 TO n
    y(i) = y(i) + y(i - 1): p = p + 1
NEXT
 
FOR i = 0 TO n
    FOR j = y(i - 1) TO y(i)
        x(j) = i: p = p + 1
s = s + 1: NEXT j, i
 
' algorithm

finish = TIMER

FOR i = n - 10 TO n - 1: PRINT x(i);: NEXT: PRINT
PRINT finish - start, s, p

OPEN "c:/REZ11.txt" FOR OUTPUT AS #2
FOR i = 1 TO n: PRINT #2, x(i): NEXT
: END

Русская Сортировка Половинами Данилин Russian Sorting Halves Danilin visualization

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

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

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

merge quick shell radix tim

Пока мир пытался ускорить быстрые алгоритмы
Россия ускорила медленные алгоритмы в 8 раз

While world was trying to speed up fast algorithms
Russia accelerated slow algorithms 8 times

and on eve of Certificate: Russian sorting halves

correctly read letter O:
Russkaya sOrtirOvka pOlOvinami

Sorting is represented as: mass moves to a distance
and it will be necessary to use results
sorts of reading same array calculate integral:

work as sum of works: load mass = displacement
and while calculated: where it requires normal sorting

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

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

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

Русская Сортировка Половинами Данилин Russian Sorting Halves Danilin visualization
Допустим требуется сортировать массив 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

Русская Сортировка Половинами Данилин Russian Sorting Halves Danilin visualization

Русская Сортировка Половинами Данилин Russian Sorting Halves Danilin visualization

Русская Сортировка Половинами Данилин Russian Sorting Halves Danilin visualization

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

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

Русская сортировка половинами ускоряет другие сортировки
за счёт перехода формулы затрат времени N^2 или N*(N-1)/2
в формулу например для 2-х частей: 2*(N/2)*((N/2)-1)/2.

Русская Сортировка Половинами Данилин Russian Sorting Halves Danilin visualization

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))
 

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

'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

деление массива на 4 части происходит мгновенно
имя q(3) будет заменено на имя попроще

но попытки разделения за 2 вложенных циклов
разбиваются о порядок точек середин 3 2 4

что приводит к массивам с 2-йными скобками
что усложняет понимание и лучше применить

говорящие переменные типа средний3
оставив 3 цикла раздельными

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

Нобелевская премия сама себя не получит
Nobel Prize will not receive itself
Le prix Nobel ne se recevra pas

rosettacode.org/wiki/Category:Sorting_Algorithms

airtucha.github.io/SortVis/
toptal.com/developers/sorting-algorithms/
sorting.at

growingwiththeweb.com/projects/sorting-visualiser/

anim.ide.sk/sorting_algorithms_1.php

algolab.valemak.com/thanos
algolab.valemak.com/
algolab.valemak.com/links

algolab.valemak.com/algolab-xlsm
 

Русская Сортировка Половинами Данилин Russian Sorting Halves Danilin visualization

Русская Сортировка Половинами Данилин Russian Sorting Halves Danilin visualization

Русская сортировка половинами важные действия визуализация
Russian sorting halves important actions visualization

 

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

сортирует 1000ооо за 0,3 секунды
сортирует миллион за 0,3 секунды
sorts 1'000'000 in 0.3 seconds
сортирует 1'000'000 за 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

C#

// RUSSIAN SORTING HALVES DANILIN 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 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;

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

// read 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
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;
}
}
}

 

Прототип сортирует интеграл букв:
и строки нижние больше верхних

N=10: DIM d$(N), a$(N), b(27)

d$(1)="ABC": d$(2)="QQQ": d$(3)="SSS": d$(4)="ZYX": d$(5)="PPP":
d$(6)="FFF": d$(7)="QBB": d$(8)="DDD": d$(9)="ZZZ": d$(10)="AAA":

FOR i=1 TO N
 c=ASC(MID$(d$(i),1,1))-64
 b(c)=b(c)+1
NEXT

FOR i=1 TO 27 STEP 3: PRINT CHR$(i+64); b(i), CHR$(i+1+64); b(i+1), CHR$(i+2+64); b(i+2): NEXT

PRINT: summa=0: FOR i=1 TO 26: summa=summa+i * b(i): NEXT
h=0: FOR i=1 TO 26
 IF b(i) > 0 THEN h=h+1
NEXT

middle=summa/h: PRINT summa, h, middle: PRINT

y=1: z=0: FOR i=1 TO N
 c=ASC(MID$(d$(i), 1, 1))-64: PRINT c; c * b(c),
 IF c * b(c) < middle THEN a$(y)=d$(i): y=y+1: ELSE a$(N-z)=d$(i): z=z+1
NEXT: PRINT: PRINT

FOR i=1 TO N: PRINT a$(i),: NEXT: PRINT
PRINT y-1

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

Замена числа 1 везде на переменную с именем
например one проверено для разных типов данных:
ускорила qb64 с 2,2 до 2,09 секунд
и замедлила pb с 0,3 до 0,4 секунд
для сортировки 1'000'000 элементов

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

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

Русская Сортировка Половинами и скорая и человеческая
замечательная задача для Олимпиад по информатике

Russian Sorting Halves and fast and human
is wonderful job for Olympiad in computer science

Русская сортировка половинами помогает изучить:

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

Данная тема развивается на форумах:

qb64forum.alephc.xyz/index.php?topic=702

bytes.com/topic/c-sharp/answers/971639-russian-sorting-halves-danilin
csharpforums.net/threads/russian-sorting-halves-danilin.4221
go4expert.com/forums/russian-sorting-halves-danilin-t35231/
forums.purebasic.com/english/viewtopic.php?f=13&t=71585
freebasic.net/forum/viewtopic.php?f=3&t=27097

 

rosettacode.org/wiki/Category:Sorting_Algorithms

 

Созданы 13 вариантов Русская сортировка половинами

1. Ускорение сортировки пузырьковой в 2 раза
добавив строки деления массива на 2 части

2. Ускорение сортировки пузырьковой в 4 раза
добавив строки деления массива на 4 части

3. Ускорение сортировки выбором в 2 раза
добавив строки деления массива на 2 части

4. Ускорение сортировки выбором в 4 раза
добавив строки деления массива на 4 части

5. Рекурсия QB64 1'000'000 за 2,2 секунды
6. Рекурсия PureBasic 1'000'000 за 0,3 секунды
7. Рекурсия C# 1'000'000 за 0,2 секунды
8. Рекурсия FreeBasic 1'000'000 за 0,15 секунды
9. QB64 сортирует интеграл букв

10. Excel ускоренная для 250 элементов
11. Excel анимационная для 250 элементов

12. Ускорение пузырьковой сортировки
делением на 4 части C#
13. Вложенные циклы и индексы индексов
 

Русская Сортировка Интегралов

Russian Sorting of Integrals

 

 

 

qb64 Seven Bubble sort for you: which do you choose? 
qb64phoenix.com/forum/showthread.php?tid=1540&pid=14341#pid14341
 

kenokeno.ucoz.ru/fips/2018618246.htm

Категория: Мои файлы | Добавил: DANILIN
Просмотров: 2987 | Загрузок: 241 | Рейтинг: 0.0/0
Всего комментариев: 0

Форма входа

Категории раздела

Поиск

Статистика


Онлайн всего: 1
Гостей: 1
Пользователей: 0
Карта мира

Данный сайт средством массовой информации не является.
Данный сайт: личный дневник, созданный в развлекательных целях.
Данный сайт азартные игры не пропагандирует и не организует.
Данный сайт ставки не принимает и выигрыши не выплачивает.
Данный сайт никакие платные услуги не предоставляет.

Сайт и автор за упущенную выгоду ответственность не несёт.
Сайт и автор за возможные убытки ответственность не несёт.

Файлы имеют цель: приоритет открытий, изобретений, формул и творчества
и тексты выражают субъективные оценочные суждения без упоминания имён.

Все тексты юридической силы не имеют и служить доказательством в суде не могут.
Все формулы возможно вывести самостоятельно и ответ автора сайта не нужен.
18+ web.archive.org/web/20230602152617///kenokeno.ucoz.ru/load/?page2

This site is not a media outlet.
This site: personal diary created for entertainment purposes.
This site promote does not and gambling not organize.
This site bets does not accept and winnings does not pay out.
This site any paid does services not provide.

Site and author for lost profits are not responsible.
Site and author for possible losses are not responsible.

Files have a target: priority of discoveries, inventions, formulas, and creativity
and texts express subjective value judgments without mentioning any names.

All texts have no legal force and as evidence in court cannot serve.
All formulas can be deduced independently & response of site author is not required.
18+ web.archive.org/web/20230602154543///kenokeno.ucoz.ru/publ/?page2

Бесплатный конструктор сайтов - uCozЯндекс.Метрика