It is currently Thu Sep 19, 2019 3:56 am

All times are UTC + 1 hour




Post new topic Reply to topic  [ 6 posts ] 
Author Message
 Post subject: Russian Sorting Halves Danilin
PostPosted: Wed Oct 17, 2018 8:08 pm 
Offline
New User
New User

Joined: Wed Oct 17, 2018 7:41 pm
Posts: 4
Russian Sorting Halves and fast and human
sorts 1'000'000 in 0.3 seconds

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
OpenConsole()
Declare RussianSortingHalvesDAV (ab, yz, part, age)

;n=1234567

If ReadFile(0, "c:/N.txt")
 n = Val(ReadString(0))
 CloseFile(0)
EndIf

age=Int(1+(Log(n)/Log(2)))
Global Dim d(n)
Global Dim a(n)

For i=1 To n
  ;d(i)=Random(n,1)
  d(i)=n-i+1;
Next

PrintN(" First 20")
For k=1 To 20: Print(" "+ d(k)): Next: PrintN("")
PrintN(" Last 10")
For k=n-9 To n : Print(" "+ d(k)): Next: PrintN("")

start=ElapsedMilliseconds()

If age > 0 :
 RussianSortingHalvesDAV(1, n, 1, age)
EndIf

finish=ElapsedMilliseconds()

PrintN("RussianSorting First 50")
For k=1 To 50: Print(" "+ d(k)): Next: PrintN("")
PrintN(" Last 20")
For k=n-19 To n : Print(" "+ d(k)): Next: PrintN("")

PrintN( "Time RussianSorting = " + Str(finish-start))

If OpenFile(0, "c:/RSH_DAV.txt")
  For k=1 To 1000 :WriteString (0, " " +d(k)): Next
  For k=n-1001 To n :WriteString (0, " " +d(k)): Next
 CloseFile(0)
EndIf

Input()
End

Procedure RussianSortingHalvesDAV (ab, yz, part, age)

If yz-ab < 1 :ProcedureReturn 0
EndIf

For i=ab To yz
summa=summa+d(i)
Next
middle=summa/(yz-ab+1)

abc=ab-1
xyz=yz+1

For j=ab To yz
If d(j) <= middle:
abc=abc+1: a(abc)=d(j)
Else
xyz=xyz-1: a(xyz)=d(j)
EndIf

Next

For w=ab To yz: d(w)=a(w): Next

If part < age :
If abc >= ab :RussianSortingHalvesDAV(ab, abc, part+1, age)
EndIf
If xyz < yz :RussianSortingHalvesDAV(xyz, yz, part+1, age)
EndIf
EndIf

EndProcedure

Russian Sorting Halves Danilin visualisation
https://www.youtube.com/watch?v=UxvSwOtpiuc
https://www.youtube.com/watch?v=9poxfAcbxFQ

Image

feature of the algorithm of the topic:
everyone is able to understand this algorithm
unlike certain incomprehensible algorithms machine sorting.

especially considering: my algorithm is pretty quick.

means using for example sorting of goods
or sorting the way people can be sure:
algorithm and quick and understandable to people.

and another feature: speeds up slow sorts
in 2 ... 4 ... 8 times dividing the bubble sort array
which makes my algorithm even more human.


Top
 Profile  
Reply with quote  
 Post subject: Re: Russian Sorting Halves Danilin
PostPosted: Thu Oct 18, 2018 7:36 am 
Offline
Enthusiast
Enthusiast
User avatar

Joined: Thu Apr 30, 2009 5:23 pm
Posts: 302
Location: Côtes d'Azur, France
It's nice you made your own sort. Image
Could you describe in which cases this sort had any advantage over other sorts ?

My understanding of your sort is the following:
you first get an average threshold for all elements.
Then you "divide and conquer" the whole batch and repeat this operations. (so it's O(N²)+O(N.log(N)) ?? I am not sure...)
If I am wrong, please explain... Else, it'a a fancy but very slow sort. (??)

You may have a look to merge sort (it's pretty human too ^^ ) or quick sort instead. :wink:

_________________
There are 2 methods to program bugless.
But only the third works fine.

Win10, Pb x64 5.70 LTS


Last edited by Fig on Thu Oct 18, 2018 10:04 am, edited 1 time in total.

Top
 Profile  
Reply with quote  
 Post subject: Re: Russian Sorting Halves Danilin
PostPosted: Thu Oct 18, 2018 9:31 am 
Offline
New User
New User

Joined: Wed Oct 17, 2018 7:41 pm
Posts: 4
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

Image

Image

Image

Russian Sorting Halves and risk management:
in 1st approximation relative to risk of 50%:

to left events with minimal risk for large participation
to right of event with maximum risk for small participation

and still easy to sort inside 2 parts
at least dividing risks into 4 parts.

Russian Sort Halves Accelerate Danilin visualisation
https://www.youtube.com/watch?v=TcwY8Ue0DKw


Top
 Profile  
Reply with quote  
 Post subject: Re: Russian Sorting Halves Danilin
PostPosted: Sat Oct 27, 2018 12:59 pm 
Offline
New User
New User

Joined: Wed Oct 17, 2018 7:41 pm
Posts: 4
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


Top
 Profile  
Reply with quote  
 Post subject: Re: Russian Sorting Halves Danilin
PostPosted: Sun Oct 28, 2018 9:15 am 
Offline
Enthusiast
Enthusiast
User avatar

Joined: Thu Apr 30, 2009 5:23 pm
Posts: 302
Location: Côtes d'Azur, France
I was wondering, how do you prevent overflow when summing all numbers ? (with big numbers or lots of elements...)

Code:
For i=ab To yz
summa=summa+d(i)
Next
middle=summa/(yz-ab+1)

_________________
There are 2 methods to program bugless.
But only the third works fine.

Win10, Pb x64 5.70 LTS


Top
 Profile  
Reply with quote  
 Post subject: Re: Russian Sorting Halves Danilin
PostPosted: Thu Sep 12, 2019 3:43 pm 
Offline
New User
New User

Joined: Wed Oct 17, 2018 7:41 pm
Posts: 4
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


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 6 posts ] 

All times are UTC + 1 hour


Who is online

Users browsing this forum: No registered users and 15 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  

 


Powered by phpBB © 2008 phpBB Group
subSilver+ theme by Canver Software, sponsor Sanal Modifiye