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

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

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

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

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



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

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

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

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

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

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

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

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

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

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

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

'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