Russian Sorting Halves Danilin

[DANILIN]

Russian Sorting Halves Danilin

Russian Sorting Halves and fast and human
sorts 1'000'000 in 2.2 seconds on QB64
sorts 1'000'000 in 0.3 seconds on PureBasic

me interested implementation of algorithm in language C#

number of elements is written to file with c:/N.txt or use variable n
array d(n) can be read from a file or synthesized in a program

Russian Sorting Halves Danilin visualisation

Russian Sorting Halves and fast and human
sorts 1'000'000 in 0.2 seconds on C# Csharp

// RUSSIAN SORTING HALVES DANILIN
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;
 
            //var rand = new Random();
            // RANDOM [1;n]
            //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 DANILIN
            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;
        }
    }
}

Russian Sorting Halves and fast and human
sorts 1'000'000 in 2.2 seconds on QB64
sorts 1'000'000 in 0.3 seconds on PureBasic
sorts 1'000'000 in 0.2 seconds on C# Csharp
sorts 1'000'000 in 0.15 seconds on Freebasic

[DANILIN]

Russian Sorting Halves Danilin visualisation

https://www.youtube.com/watch?v=UxvSwOtpiuc
https://www.youtube.com/watch?v=9poxfAcbxFQ

[DANILIN]

a 4 times acceleration proof

// Russian Sorting Halves 4 part accelerate bubble sorting 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace octoberApp
{
    class Program
    {
        static int n;
        static double[] d;
        static double[] a;
        static double[] v;
        static int[] q;
 
        static void Main(string[] args)
        {
            n = 57539; 
 
            d = new double[n+1];
            a = new double[n+1];
            v = new double[n+1];
            q = new int[5+1];
            var rand = new Random();
            for (int i = 1; i <= n; i++)
                d[i] = Math.Truncate(rand.NextDouble() * n);
 
            for (int i = 1; i <= 10; i++)
                Console.Write("{0} ", d[i]);
            Console.WriteLine();
 
            for (int i = n - 9; i <= n; i++)
                Console.Write("{0} ", d[i]);
            Console.WriteLine();
            Console.WriteLine();
 
            var start = DateTime.Now;
            var s = 0;
            //ALL
            double summa = 0;
            for (int i = 1; i <= n; i++)
                summa += d[i];
            double middle = summa / n;
            var y = 1;
            var z = 0;
 
            for (int i = 1; i <= n; i++)
                if (d[i] < middle)
                {
                    a[y] = d[i]; y++;
                }
                else
                {
                    a[n - z] = d[i];
                    z++;
                }
 
            q[3] = y - 1;
            Console.WriteLine("ALL middle = {0}", middle);
 
            for (int i = 1; i <= 10; i++)
                Console.Write("{0} ", a[i]);
            Console.WriteLine();
            Console.WriteLine();
            for (int i = n - 9; i <= n; i++)
                Console.Write("{0} ", a[i]);
            Console.WriteLine();
            Console.WriteLine();
 
            // 1 FROM 2
            summa = 0;
            for (int i = 1; i <= q[3]; i++)
                summa += a[i];
 
            middle = summa / q[3];
            y = 1;
            z = 0;
            Console.WriteLine("1 FROM 2 = {0} 1 ...{1}", middle, q[3]);
 
            for (int i = 1; i <= q[3]; i++)
                if (a[i] < middle)
                {
                    v[y] = a[i]; y++;
                }
                else
                {
                    v[q[3] - z] = a[i];
                    z++;
                }
 
            for (int i = 1; i <= 10; i++)
                Console.Write("{0} ", v[i]);
            Console.WriteLine();
            for (int i = q[3] - 9; i <= q[3]; i++)
                Console.Write("{0} ", v[i]);
            Console.WriteLine();
            Console.WriteLine();
 
            q[2] = y - 1;
 
            // 2 FROM 2
            summa = 0;
            for (int i = q[3] + 1; i <= n; i++)
                summa += a[i];
            middle = summa / (1 + n - q[3]);
            y = q[3];
            z = 0;
            Console.WriteLine("2 FROM 2 = {0} {1}...{2}", middle, q[3] + 1, n);
            for (int i = q[3]; i <= n; i++)
                if (a[i] < middle)
                {
                    v[y] = a[i]; y++;
                }
                else
                {
                    v[n - z] = a[i];
                    z++;
                }
            for (int i = q[3]; i <= q[3] + 10; i++)
                Console.Write("{0} ", v[i]);
            Console.WriteLine();
            for (int i = n - 9; i <= n; i++)
                Console.Write("{0} ", v[i]);
            Console.WriteLine();
            Console.WriteLine();
 
            q[4] = y - 1;
            q[1] = 2;
            q[5] = n;
 
            //BUBBLE
            Console.WriteLine("1= {0} 2= {1} 3= {2} 4= {3} 5= {4}", 1, q[2], q[3], q[4], n);
            Console.WriteLine();
 
            for (int t = 1; t <= 4; t++)
                for (int i = q[t] - 1; i <= q[t + 1]; i++)
                    for (int j = i + 1; j <= q[t + 1]; j++)
                        if (v[i] > v[j])
                        {
                            var x = v[i];
                            v[i] = v[j];
                            v[j] = x;
                            s++;
                        }
 
            var finish = DateTime.Now;
 
            for (int i = 1; i <= 10; i++)
                Console.Write("{0} ", v[i]);
            Console.WriteLine();
 
            for (int i = n - 9; i <= n; i++)
                Console.Write("{0} ", v[i]);
            Console.WriteLine();
            Console.WriteLine();
            Console.WriteLine("DA RUS 4 {0} second swap {1}", (finish - start).TotalSeconds, s);
 
 
            var outFile = new System.IO.StreamWriter("RUoct.txt");
            outFile.WriteLine("DA RUS 4 {0} second swap {1}", (finish - start).TotalSeconds, s);
            outFile.WriteLine("{0} 4 parts bubble ", n);
 
            for (int i = 1; i <= n / 2; i++)
                outFile.WriteLine(v[i]);
            for (int i = n / 2; i <= n; i++)
                outFile.WriteLine(v[i]);
 
            outFile.Close();
 
            start = DateTime.Now;
            s = 0;
 
            for (int i = 1; i <= n; i++)
                for (int j = i + 1; j <= n; j++)
                    if (d[i] > d[j])
                    {
                        var x = d[i];
                        d[i] = d[j];
                        d[j] = x;
                        s++;
                    }
            finish = DateTime.Now;
 
            Console.WriteLine("BUBBLE {0} second swap {1}", (finish - start).TotalSeconds, s);
 
            Console.WriteLine("Press any key");
            Console.ReadKey();
        }
    }
}

a 4 times acceleration proof

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

[DANILIN]

We learn C# knowing Basic & Excel & qb64

? Why C# & Basic & Excel & qb64?
because C# & qb64 are compiled

I have a C# csc.exe compiler in Win7
and compile through an individual bat

Excel: even micro-sized environments
Basic: qb64 compatible with Win7

qb64 quadratic equation:

' quadratic equation QB64 DAV 
 
INPUT "INPUT A"; A
INPUT "INPUT B"; B
INPUT "INPUT C"; C
 
D = B ^ 2 - 4 * A * C
 
IF D < 0 THEN PRINT "D<0 ": END
 
PRINT "ANSWER: "
PRINT "D ="; D
 
X1 = (-B + SQR(D)) / (2 * A)
X2 = (-B - SQR(D)) / (2 * A)
 
PRINT "X1 ="; X1
PRINT "X2 ="; X2
 
END

C# quadratic equation without checking d<0:

// quadratic equation C# DAV  
using System;
using System.Text;
using System.IO;
namespace DAV 
{
    class Program
        {
    static void Main(string[] args)
    {
Console.Write("INPUT A: ");
long a = Convert.ToInt32(Console.ReadLine());
Console.Write("INPUT B: ");
long b = Convert.ToInt32(Console.ReadLine());
Console.Write("INPUT C: ");
long c = Convert.ToInt32(Console.ReadLine());
 
long d = (b * b - 4 * a * c);
Console.WriteLine("ANSWER: ");
Console.Write("D = "); 
Console.WriteLine(d);
 
var x1 = (-b + Math.Sqrt(d)) / (2 * a);
var x2 = (-b - Math.Sqrt(d)) / (2 * a);
 
Console.Write("X1 = "); 
Console.WriteLine(x1);
Console.Write("X2 = "); 
Console.WriteLine(x2);
 
        Console.ReadKey();
        }
    }
}

excel quadratic equation without checking d<0:
excel: copy and paste in A1

6
7
2
=A2^2-4*A1*A3
=(-A2+(A4^(1/2)))/(2*A1)
=(-A2-(A4^(1/2)))/(2*A1)

further need to examine conditions
creating a toy "guess number"

[DANILIN]

qb64 for 1 minute created main lines and for minutes issued
C# in 3 hours created by internet tips with new ideas

'qb64 dav guess number from 0 to 100 with counting of steps 
RANDOMIZE TIMER
s = INT(RND * 100)
t = 0
 
10 PRINT: t = t + 1:
INPUT "your variant"; a
 
IF a < s THEN PRINT "need MORE": GOTO 10
IF a > s THEN PRINT "need less": GOTO 10
PRINT "win by"; t; "steps"
END

'//C# dav guess number from 0 to 100 with counting of steps 
using System;
using System.Text;
namespace DAV 
{
    class Program
        {
    static void Main(string[] args) 
    {
Random rand = new Random();
int s = rand.Next(100);
int t = 0;
 
dav:
Console.WriteLine();
t++;
 
Console.Write("your variant ");
string d = Console.ReadLine();
int a = Convert.ToInt32(d);
 
if(a > s)
    {
    Console.WriteLine("need less");
    goto dav;
    }
else if(a < s)
    {
    Console.WriteLine("need MORE");
    goto dav;
    }
Console.Write("win by ");
Console.Write(t);
Console.Write(" steps"); 
        Console.ReadKey();
        }
    }
}

[DANILIN]

'milliard & billion qb64 DAV guess 1 number of 1'OOO'000'ooo by 30 steps
 
RANDOMIZE TIMER
h2 = INT(RND * 10 ^ 9)
h1 = 0
c = INT(RND * h2) 'comp
h = INT(RND * h2) 'human
t = 0
 
10 t = t + 1
PRINT t, c, h,
 
IF h < c THEN PRINT "MORE": a = h: h = INT((h + h2) / 2): h1 = a: GOTO 10
IF h > c THEN PRINT "less": a = h: h = INT((h1 + h) / 2): h2 = a: GOTO 10
PRINT "win by "; t; " steps"
END

C# compiler feature noticed
remark that there is a mistake at beginning of program
may mean a lack of characters } at end

example for a range from 0 to 100

1    40    11    MORE
2    40    55    less
3    40    33    MORE
4    40    44    less
5    40    38    MORE
6    40    41    less
7    40    39    MORE
8    40    40    win by 8 steps

BasiC# qbc# C##


Online C# compiler detected
and dozens more languages without qbasic
working without registration

and there typing program is possible
save state with program

for example program C # Billion
guessing 1 of 1'000'OOO'ooo
=log(10^9;2) in 30 moves

rextester.com/JRGX29275

//milliard & billion C# DAV guess 1 number of 1000000000 by 30 steps  
using System;
using System.Text;
namespace DAV
{
    class Program
    {
    static void Main(string[] args)
    {
int h2 = 1000000000;//or 500
int h1 = 0;
Random rand = new Random();
int c = rand.Next(h2); //computer
int h = rand.Next(h2); //human or h2/2;
int t = 0;
 
dav:
t++;
Console.WriteLine();
Console.Write(t);
Console.Write("  ");
Console.Write(c);
Console.Write("  ");
Console.Write(h);
Console.Write("  ");
 
if(h < c)
    {
    Console.Write("MORE");
    int a = h;
    h = (h + h2) / 2;
    h1 = a;
    goto dav;
    }
else if(h > c)
    {
    Console.Write("less");
    int a = h;
    h = (h1 + h) / 2;
    h2 = a;
    goto dav;
    }
Console.Write("win by ");
Console.Write(t);
Console.Write(" steps");
        Console.ReadKey();
        }
    }
}

Searching see programs stored ... 5 years
and for certain still there is an online compiler C#
and really are through Yandex search

but since interested in graphics
while I use cs & bat

[DANILIN]

we draw 5D relief creating a random array of heights

on QB64 in 5 minutes and plus in an hour
beauty and versatility

[IMG]reliefqb.gif[/IMG]

' 5d relief and array
SCREEN 12: RANDOMIZE TIMER: DIM a(12,12)
FOR t=1 TO 12 ' quantity
    FOR x=1 TO 12: FOR y=1 TO 12
a(x,y)=INT(RND*20)'heights
    NEXT: NEXT: CLS
    FOR y=1 TO 12: FOR x=1 TO 11
LINE (50+20*x+20*y, 400-20*y-a(x,y))-(50+20*(x+1)+20*y, 400-20*y-a(x+1,y)), y
    NEXT: NEXT
    FOR x=1 TO 12: FOR y=1 TO 11
LINE (50+20*x+20*y, 400-20*y-a(x,y))-(50+20*(x+1)+20*y, 400-20*(y+1)-a(x,y+1)), x
    NEXT: NEXT:SLEEP 1
NEXT
END

on C# pendulum program is used
because of what remained incomprehensible lines about timer
and random function depends on outside / inside cycles
and to understand another program created random

how to clear screen is still unclear and builds slowly
and it is unclear how to set color of lines by variables

[IMG]reliefcs.gif[/IMG]

still as task manager shows
simple C# program or array fills memory
and only at end does memory clear line save

//RELIEF
using System;
using System.Drawing;
using System.Windows.Forms;
class RELIEF
{
Timer timer; // it is not clear
Form form;
 
int[,] a = new int[22, 22];
static void Main(string[] args) 
{
var p = new RELIEF();
}
public RELIEF()
{
    form = new Form() { Text = "RELIEF", Width = 600, Height = 360 };
    timer = new Timer() { Interval = 200 }; // it is not clear
    timer.Tick += delegate(object sender, EventArgs e) // it is not clear
    {
    Random rand = new Random();
// heights
    for (int x = 1; x <=12; x++)
    {
    for (int y = 1; y <=12; y++)
    a[x,y]=rand.Next(20);
    }
// parallels X
    for (int y = 1; y <=12; y++)
    {
    for (int x = 1; x <=11; x++)
        {
    var x1 = 50 + 20*x + 20*y; 
    var y1 = 300 - 20*y - a[x,y];
    var x2 = 50 + 20*(x+1) + 20*y;
    var y2 = 300 - 20*y - a[x+1,y];
 
    Bitmap dblBuffer = new Bitmap(form.Width, form.Height);
    Graphics g = Graphics.FromImage(dblBuffer);
    Graphics f = Graphics.FromHwnd(form.Handle);
 
    g.DrawLine(Pens.Red, new Point(x1, y1), new Point(x2, y2));
//    f.Clear(Color.Green); // clear screen
    f.DrawImage(dblBuffer, new Point(0, 0));
     }
    }
// parallels Y
    for (int x = 1; x <=12; x++)
    {
    for (int y = 1; y <=11; y++)
    {
    var x1 = 50 + 20*x + 20*y; 
    var y1 = 300 - 20*y - a[x, y];
    var x2 = 50 + 20*(x+1) + 20*y;
    var y2 = 300 - 20*(y+1) - a[x, y+1];
 
    Bitmap dblBuffer = new Bitmap(form.Width, form.Height);
    Graphics g = Graphics.FromImage(dblBuffer);
    Graphics f = Graphics.FromHwnd(form.Handle);
 
    g.DrawLine(Pens.Red, new Point(x1, y1), new Point(x2, y2));
//    f.Clear(Color.Green); // clear screen
    f.DrawImage(dblBuffer, new Point(0, 0));
    }
    }
Array.Clear(a, 0, 22); // clears memory
    };
    timer.Start(); // it is not clear
    Application.Run(form);
    }     
}

besides C# pendulum is C # diagonal simpler
and no other C# program is included
so as in basic: 1 file = 1 program

that's why my given 5D relief program is important.
drawing at least something predictable
and at same time we study nested loops

and I'm still looking for compilable graphics programs:

1 file = 1 program
1bas=1exe & 1cs=1exe

and already created studies about strings

[DANILIN]

c# version of "guess my number game" 1 line

using System; using System.Text;namespace GURU { class Program { static void Main(string[] args) { Random rand = new Random(); int Russia = 0; int n = 0; int num = 0; dav: if(Russia == 0) {Russia = 2222; num = rand.Next(100)+1; goto dav; }else if (Russia != 0) {Console.Write("? "); n = Convert.ToInt32(Console.ReadLine());} if (n < num) { Console.WriteLine("MORE"); goto dav;}else if (n > num) { Console.WriteLine("less"); goto dav;}else if (n == num) {Console.Write("da"); Console.ReadKey(); }else goto dav;}}}// DANILIN Russia 9-9-2019 guessnum.cs

using System; using System.Text;namespace GURU { class Program { static void Main(string[] args) { Random rand = new Random(); int Russia = 0; int n = 0; int num = 0; dav: if(Russia == 0) {Russia = 2222; num = rand.Next(100)+1; goto dav; }else if (Russia != 0) {Console.Write("? "); n = Convert.ToInt32(Console.ReadLine());} if (n < num) { Console.WriteLine("MORE"); goto dav;}else if (n > num) { Console.WriteLine("less"); goto dav;}else if (n == num) {Console.Write("da"); Console.ReadKey(); }else goto dav;}}}// DANILIN Russia 9-9-2019 guessnum.cs

c# version of "guess my number game" 1 line

qbasic version of "guess my number game" 1 line

1 IF Russia = 0 THEN Russia = 2222: RANDOMIZE TIMER: num = INT(RND * 100) + 1: GOTO 1 ELSE IF Russia <> 0 THEN INPUT n: IF n < num THEN PRINT "MORE": GOTO 1 ELSE IF n > num THEN PRINT "less": GOTO 1 ELSE IF n = num THEN PRINT "da": END ELSE GOTO 1 'DANILIN Russia 9-9-2019 guessnum.bas

1 IF Russia = 0 THEN Russia = 2222: RANDOMIZE TIMER: num = INT(RND * 100) + 1: GOTO 1 ELSE IF Russia <> 0 THEN INPUT n: IF n < num THEN PRINT "MORE": GOTO 1 ELSE IF n > num THEN PRINT "less": GOTO 1 ELSE IF n = num THEN PRINT "da": END ELSE GOTO 1 'DANILIN Russia 9-9-2019 guessnum.bas

qbasic version of "guess my number game" 1 line