Russian Sorting Halves Danilin

Discussion in 'C++' started by DANILIN, Oct 24, 2018.

  1. DANILIN

    DANILIN New Member

    Joined:
    Oct 24, 2018
    Messages:
    3
    Likes Received:
    1
    Trophy Points:
    3
    Gender:
    Male
    Home Page:
    https://www.youtube.com/channel/UC8Ig3Mp2RA-2aj79-NsI1mw/videos?sub_confirmation=1
    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++
     
  2. DANILIN

    DANILIN New Member

    Joined:
    Oct 24, 2018
    Messages:
    3
    Likes Received:
    1
    Trophy Points:
    3
    Gender:
    Male
    Home Page:
    https://www.youtube.com/channel/UC8Ig3Mp2RA-2aj79-NsI1mw/videos?sub_confirmation=1
    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;
    }}}
     
    Last edited: Jul 27, 2021
  3. DANILIN

    DANILIN New Member

    Joined:
    Oct 24, 2018
    Messages:
    3
    Likes Received:
    1
    Trophy Points:
    3
    Gender:
    Male
    Home Page:
    https://www.youtube.com/channel/UC8Ig3Mp2RA-2aj79-NsI1mw/videos?sub_confirmation=1
    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
     
    shabbir likes this.

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice