a 4 times acceleration proof qb64
and me interested implementation of algorithm in language Python
'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
[Image: rspvip.gif]
1:50 Russian Sort Halves Accelerate Danilin visualisation
a 4 times acceleration proof qb64
[Image: da44bubble.png]
division of array into 4 parts occurs instantly
name q(3) will be replaced by a simpler name
but separation attempts for 2 nested loops
broken about order of midpoints 3 2 4
which leads to arrays with 2nd brackets
which complicates understanding and better apply
speaking variables of type middle3
leaving 3 cycles separate
and me interested implementation of algorithm in language Python
Russia looks world from future. Big data is peace data
Nobel Prize will not receive itself
Nobelevskaya premiya sama sebya ne poluchit
Нобелевская премия сама себя не получит
Le prix Nobel ne se recevra pas
Nobelpreis wird sich nicht erhalten
Il Premio Nobel non ricevera se stesso