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 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
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
Code:
// 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;
}
}
}
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
Comment