Среда, 21.11.2018, 09:38
Приветствую Вас Гость | RSS

Анти лотерейный математичесий сайт и всё БЕСПЛАТНО

Anti Lottery math site all FREE anti casino против казино

Карта мира Конкурс ставок IntelBet мой ВКонтакте КеноКено КЕНО ЮТЮБ KENO mini YOUTUBE Яндекс.Метрика Гость,

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

НЕТ рекламы НЕТ партнёрских НЕТ рефералов NO advertising NO partners NO referrals pas de publicite pas de partenaires pas de references ешқандай жарнама ешқандай серіктестер жоқ реферал

IQ бесплатно КЕНО ЮТЮБ 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

CITIZENS of USA and EU to me DONATE please: almost $ 0.8 WMZ = € 0.7 WME =
= pressed picture DONATE above or WMZ Z636495154357 WME E123268917690

BÜRGERS der USA und der EU zu mir SCHENKEN bitte: Der WMZ von fast 0.8 $ = der WME von 0.7 € =
= hat den picture SCHENKEN oben gedrückt oder WMZ Z636495154357 WME E123268917690

les CITOYENS des Etats-Unis et d'UE à moi DONNENT s'il vous plaît : WMZ de presque 0.8$ = WME de 0.7€ =
= a appuyé sur picture DONNENT au-dessus ou WME E123268917690 WMZ Z636495154357

время застолбить за собой новое слово интиграаль
интИГРАаль = интеграл + игра + грааль = ИНТиграАЛЬ

time to stake a new word
temps de jeu un nouveau mot
Zeit um dem Spiel ein neues Wort

intigraal
intIGRAal = integral + igra + graal = INTigraAL

Уважаемые посетители данного сайта из Кремниевой Долины!

Видя все посещения данного сайта через карту мира

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

составляет $1 Webmoney скопирован из кошелька Z636495154357

Dear visitors of this site from Silicon Valley!

Seeing all visits to this site through world map

cost of each day visiting this site from Silicon Valley

is $ 1 Webmoney copied from wallet Z636495154357

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

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

Русская Сортировка Половинами и quicksort быстрая сортировка qbasic и МЫ
[ Скачать с сервера (4.55 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

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

пузырьковая 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# Csharp 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

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

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

http://growingwiththeweb.com/projects/sorting-visualiser/

http://algolab.valemak.com/thanos
http://algolab.valemak.com/
http://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

http://rosettacode.org/wiki/Category:Sorting_Algorithms

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

http://growingwiththeweb.com/projects/sorting-visualiser/

http://anim.ide.sk/sorting_algorithms_1.php

http://algolab.valemak.com/thanos
http://algolab.valemak.com/
http://algolab.valemak.com/links

http://algolab.valemak.com/algolab-xlsm
https://drive.google.com/open?id=1Nrf6WrAsaWLcMAToXLkBa-sr0YLRBDts

Русская Сортировка Половинами Данилин 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# Csharp

// RUSSIAN SORTING HALVES DANILIN C# Csharp
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

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

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

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

https://qb64.org/forum/index.php?board=6.0

https://python-forum.io/Forum-General-Coding-Help

https://freebasic.net/forum/viewforum.php?f=3

https://go4expert.com/forums/cpp/

http://forums.purebasic.com/english/viewforum.php?f=13

http://csharpforums.net/forumdisplay.php/79-C-General-Discussion

http://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# Csharp 1'000'000 за 0,2 секунды
8. Рекурсия FreeBasic 1'000'000 за 0,15 секунды
9. QB64 сортирует интеграл букв

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

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

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

Форма входа

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

Поиск

Статистика


Онлайн всего: 1
Гостей: 1
Пользователей: 0
Бесплатный конструктор сайтов - uCozЯндекс.Метрика