1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Russian Sorting Halves Danilin

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

  1. DANILIN

    DANILIN New Member

    Joined:
    Oct 24, 2018
    Messages:
    2
    Likes Received:
    0
    Trophy Points:
    1
    Gender:
    Male
    Home Page:
    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:
    2
    Likes Received:
    0
    Trophy Points:
    1
    Gender:
    Male
    Home Page:
    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
     

Share This Page