Russian Sorting Halves Danilin - Printable Version +- Python Forum (https://python-forum.io) +-- Forum: Python Coding (https://python-forum.io/forum-7.html) +--- Forum: General Coding Help (https://python-forum.io/forum-8.html) +--- Thread: Russian Sorting Halves Danilin (/thread-13545.html) Pages:
1
2
|
Russian Sorting Halves Danilin - DANILIN - Oct-20-2018 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 SUBRussian 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 RE: Russian Sorting Halves Danilin - ichabod801 - Oct-20-2018 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. RE: Russian Sorting Halves Danilin - DANILIN - Oct-20-2018 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 RE: Russian Sorting Halves Danilin - DANILIN - Oct-27-2018 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 RE: Russian Sorting Halves Danilin - Larz60+ - Oct-27-2018 Quote:Ichabod wrote:Also please note that the code you show is not 'C', but appears to be Basic or some derivative thereof. RE: Russian Sorting Halves Danilin - DANILIN - Oct-27-2018 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 RE: Russian Sorting Halves Danilin - Larz60+ - Oct-27-2018 This is more interesting on second look. Do you have comparison information to other sort algorithms? RE: Russian Sorting Halves Danilin - DANILIN - Oct-27-2018 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 RE: Russian Sorting Halves Danilin - DANILIN - Oct-27-2018 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] RE: Russian Sorting Halves Danilin - Larz60+ - Oct-27-2018 try against quicksort? |