448,742 Members | 1,807 Online
Need help? Post your question and get tips & solutions from a community of 448,742 IT Pros & Developers. It's quick & easy.

# Russian Sorting Halves Danilin

 P: 16 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 Expand|Select|Wrap|Line Numbers // 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 Oct 30 '18 #1
7 Replies

 P: 16 Russian Sorting Halves Danilin visualisation https://www.youtube.com/watch?v=UxvSwOtpiuc https://www.youtube.com/watch?v=9poxfAcbxFQ Oct 30 '18 #2

 P: 16 a 4 times acceleration proof Expand|Select|Wrap|Line Numbers // 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 Oct 30 '18 #3