Русская сортировка половинами: человеческая сортировка быстрее в 4 раза и МЫ
Цель: заинтересовать народ созданием программы Русская сортировка половинами
на других любых языках программирования
Особенность программы для ЭВМ «Русская сортировка половинами»:
уникальная картина сортировки и ускорение алгоритмов сортировки.
Допустим требуется сортировать массив N=11 чисел,
в том числе являющийся частью ранее частично сортированного большего массива.
Массив d(1,1…N)
| 2 | 8 | 1 | 6 | 7 | 10 | 4 | 11 | 9 | 3 | 5 |
Среднее значение: 7 как сумма данных ячеек делить на число ячеек
| 2 | 8 | 1 | 6 | 7 | 10 | 4 | 11 | 9 | 3 | 5 | Исходный массив d(1,1…N) | ||
| Предыдущих ячеек: 0 | |||||||||||||
| 2 | 2 < 7 в начало | счётчик = 1 | |||||||||||
| 2 | 8 | 8 >= 7 в конец | счётчик = 1 | ||||||||||
| 2 | 1 | 8 | 1 < 7 в начало | счётчик = 2 | |||||||||
| 2 | 1 | 6 | 8 | 6 < 7 в начало | счётчик = 3 | ||||||||
| 2 | 1 | 6 | 7 | 8 | 7 >= 7 в конец | счётчик = 3 | |||||||
| 2 | 1 | 6 | 10 | 7 | 8 | 10 >= 7 в конец | счётчик = 3 | ||||||
| 2 | 1 | 6 | 4 | 10 | 7 | 8 | 4 < 7 в начало | счётчик = 4 | |||||
| 2 | 1 | 6 | 4 | 11 | 10 | 7 | 8 | 11>= 7 в конец | счётчик = 4 | ||||
| 2 | 1 | 6 | 4 | 9 | 11 | 10 | 7 | 8 | 9 >= 7 в конец | счётчик = 4 | |||
| 2 | 1 | 6 | 4 | 3 | 9 | 11 | 10 | 7 | 8 | 3 < 7 в начало | счётчик = 5 | ||
| 2 | 1 | 6 | 4 | 3 | 5 | 9 | 11 | 10 | 7 | 8 | 5 < 7 в начало | счётчик = 6 | |
Массив d(2,1…N) и счётчик = 6
| 2 | 1 | 6 | 4 | 3 | 5 | 9 | 11 | 10 | 7 | 8 |
Любая из левых 6 ячеек меньше, чем любая из правых 5 ячеек.
Массив d(2,1…N) условно делится на 2 части:
| 2 | 1 | 6 | 4 | 3 | 5 | и | 9 | 11 | 10 | 7 | 8 |
и ячейки проходят ещё циклы независимо друг от друга,
сохраняя непрерывность массива d(2,1…N) ,
однако даже в данном виде после 1-го цикла
ускоряется работа человеческих алгоритмов сортировки
временной сложности N^2 в 2 раза
и после 2-го цикла ускоряется работа человеческих алгоритмов сортировки
временной сложности N^2 в 4 раза.
Тестирование на одинаковых массивах
Сортировка Пузырьковая (bubble): сравниваются элементы без смен равных.
Сортировка Выбором (select): нахождение минимума и смена с текущим элементом.
Русская сортировка половинами: проверка ускорения сортировок пузырьковой или выбором, используя деление исходного массива на 2 части, включает переменные без индекса или цикл: улучшенная пузырьковая, где массив делится на 2 части и также улучшается сортировка выбором и другие человечески понятные сортировки и возможно делить массив на 4 части и на 8 частей массово понимая алгоритм.
Сравнение формул для оценки максимального ускорения других сортировок
| русская сортировка 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 |
100ооо шт.
| русскаясортировка 4 части | 70 | секунд |
| русскаясортировка 2 части | 170 | секунд |
| пузырьковая bubble | 230 | секунд |
| выбором select | 140 | секунд |
| русская сортировка выбором 2 части | 105 | секунд |
| русскаясортировка выбором 4 части | 67 | секунд |
1000 шт.
| русскаясортировка 4 части | циклы 135048 | смены 39725 |
| русскаясортировка 2 части | циклы 261342 | смены 92805 |
| пузырьковая bubble | циклы 499500 | смены 227585 |
| выбором select | циклы 999 | смены 6346 |
| русскаясортировка выбором 2 части | циклы 999 | смены 4406 |
| русскаясортировка выбором 4 части | циклы 999 | смены 3811 |
10000 шт.
| русскаясортировка выбором 4 части | циклы 10000 | смены 48736 |
| русскаясортировка выбором 2 части | циклы 10000 | смены 67704 |
| выбором select | циклы 10000 | смены 97888 |
текстовые строки
| русскаясортировка 2 части | 1000 строк | циклы 264280 | смен 137131 |
| пузырьковая bubble | 1000 строк | циклы 499500 | смены 264139 |
| русскаясортировка 2 части | 100ооо строк | 390 | секунд |
| пузырьковая bubble | 100ооо строк | 650 | секунд |
Во всех тестах специально формировался массив,
где Русская сортировка половинами теоретически работает наиболее медленно
и всё одно Русская сортировка половинами ускоряет другие сортировки
за счёт перехода формулы затрат времени N^2
в формулу например для 2-х частей: 2*(N/2)*((N/2)-1)/2.
Русская сортировка половинами требует данные:
c:/N.txt = только количество элементов и
c:/ISX.txt = элементы в столбец в требующемся количестве возможно создать в excel
=случмежду(1000;100000)
и скопировав вставить в текст 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
Цель: заинтересовать народ созданием программы Русская сортировка половинами
на других любых языках программирования
ссылка на оригинал статьи https://habr.com/post/420755/
Добавить комментарий