Python Forum

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 Python

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

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
https://www.youtube.com/watch?v=UxvSwOtpiuc
https://www.youtube.com/watch?v=9poxfAcbxFQ

[Image: rusortpol10.gif]

me interested implementation of algorithm in language Python

We're not going to implement it for you. But if you try to implement it and run into problems we'd be happy to help.

theoretically forum people should strive prove:

? python is faster than basic ?

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

? python is slower than basic ?

---

O(N) = 3*N*LOG(N;2)

requires recalculation of entire array
and further distribution of entire array
and further return of sub-array back are required.

and number of distributions takes into account division by halves.
proves visualization and counters.

O(N) = 3*N*LOG(N;2)

Currently 8 options are created
Russian sorting halves:

1. Acceleration of bubble sorting by 2 times
adding a few lines code by dividing array into 2 parts

2. Acceleration of bubble sorting 4 times
adding a few lines code by dividing array into 4 parts

3. Acceleration of selection sorting by 2 times
adding a few lines code by dividing array into 2 parts

4. Acceleration of selection sorting by 4 times
adding a few lines code by dividing array into 4 parts

5. Recursive version of QB64 1'000'000 in 2.2 seconds
6. Recursive version of PureBasic 1'000'000 in 0.3 seconds

7. Excel animation version for 250 items on 150 second
8. Excel fast version for 250 items on 5 second

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

Quote:Ichabod wrote:
We're not going to implement it for you. But if you try to implement it and run into problems we'd be happy to help.

Also please note that the code you show is not 'C', but appears to be Basic or some derivative thereof.

I present a variant of C# combining 3 implementations.
? C# program is more understandable than basic?

// 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);

            // REAN 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;
        }
   }
}

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
sorts 1'000'000 in 0.15 seconds on FreeBasic

This is more interesting on second look. Do you have comparison information to other sort algorithms?

program contains blocks to enable same array from disk

or for inverse array
or for random numbers

starting between a lines
start = TIMER
...
finish = TIMER

it is possible to substitute any sorting algorithm
using N elements of d(n) array

and I recall main feature:
Russian Sorting Halves and fast and human

my test results:
where bubble and select show a hundred seconds
there Russian sorting halves shows about a second

and really machine sorting of incomprehensible 99.99% of people
show 2 times better than my sorting
literally like comparing formulas with logarithms

---

"where bubble and select show a hundred seconds"

meaning 100,000 items

for 1'000'000 elements
bubble and select hang for long

then for 100'000 items
Russian sorting halves sorts for 0.02 seconds

applying inside my above C# program
bubble sort inside time control
with removing recursion

results: 100'000 sorted 60 seconds bubble

at same time it proves how easy it is to adapt my development
to test any sorting algorithms using 3 methods

however 100,000 items
Russian sorting halves sorts in 0.015 seconds

[Image: rshemblems.png]

try against quicksort?