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 Code: ' Russian Sorting Halves Danilin DECLARE SUB RussianSortingHalvesDAV (ab!, yz!, part!, age!) CLOSE OPEN "c:/N.txt" FOR INPUT AS #1 INPUT #1, n 'n=1234567 age = 1 + LOG(n) / LOG(2) PRINT n DIM SHARED d(n) 'AS LONG DIM SHARED a(n) 'AS LONG 'OPEN "c:/ISX.txt" FOR INPUT AS #2 'FOR i=1 TO n: INPUT #2, d(i): NEXT 'FOR i = 1 TO n: d(i) = n - i + 1: NEXT ' INT(RND*n) FOR i = 1 TO n: d(i) = INT(RND * n): NEXT ' FOR k = 1 TO 20: PRINT d(k);: NEXT: PRINT: PRINT FOR k = n - 19 TO n: PRINT d(k);: NEXT: PRINT: PRINT start = TIMER IF age > 0 THEN CALL RussianSortingHalvesDAV(1, n, 1, age) END IF finish = TIMER PRINT finish - start; "second ": PRINT OPEN "c:/=RuSortHalves_dav.txt" FOR OUTPUT AS #3 PRINT #3, finish - start; "second " PRINT #3, n; "elements", "RECURSION" FOR i = 1 TO 22: PRINT #3, d(i): NEXT FOR i = n - 22 TO n: PRINT #3, d(i): NEXT FOR k = 1 TO 20: PRINT d(k);: NEXT: PRINT: PRINT FOR k = n - 19 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 Russian Sorting Halves Danilin visualisation me interested implementation of algorithm in language C++
news: Russian Sorting Halves and fast and human 9. Recursive version of C# Csharp 1'000'000 in 0.2 seconds resume: 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 Code: 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; }}}
c# version of "guess my number game" 1 line Code: 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 Code: 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
