Skip to main content
GameDev.net gamedev.net
🔒 Locked

New sorting algorithm

Started by BakaShinji Apr 23, 2002 at 2:46 AM 154 replies 10.9k views
Original Post
BakaShinji
BakaShinji
Speaking of the slowest sorting algorithm... I came up with a really fast sorting algorithm, and in most cases it''s faster than all previous ones. Being only a high school student though, I have no clue where to submit it. I''ve had this sorting algorithm for at least half a year now, and I''m still lost as to where to give it to. My parents tried to milk money with it, but after learning the hard way (letting them hire lawyers to find somewhere to sell it to, of course, which is nowhere... they spent quite a bit of money on them) that they can''t get money out of a sorting algorithm, they''ve been quite less cooperative. My objective is to allow people to use it freely, while safely making a record that I am the original (I hope) author of it, so that I can write about it in resumes and the such. I tried talking to my math teacher, who is the comp sci department head at one of the universities here, but I don''t know how trustable he is, as is any prof... I tried getting a software patent, but it costs $3000-25,000 USD, and... well... Canada''s poor, and so am I. Anybody know a good place to submit this thing? Thanks in advance
ragonastick
ragonastick
Name it after yourself, make a tutorial about it with your name in it. If it is good, then people will associate you with it because they read your tutorial and refer to it as "The BakaShinji sort". On the other hand, if someone has already done something similar to this and you don''t know about it, it is best that you don''t steal credit from them - and I doubt they would have patented it or anything, so if you did then it would be you who was the thief

If you want to put it on your resume, I don''t think that seeing a patent number would make them believe it any more or less. If you could write: "Do you know the BakaShinji sort? Well I''m BakaShinji", and it would probably have even more of an effect.

Trying is the first step towards failure.
Trying is the first step towards failure.
BakaShinji
BakaShinji
Well I told my comp sci teacher about it, and he calls it the ARaySort, because my name is Ray

I already made a sample program for it... So maybe it''d be safe to make a webpage for it and release it? I don''t know maybe I should try... But... "Trying is the first step towards failure." <- eek
Ziphnor
Ziphnor
If i were you, i would submit an article covering this algorithm(covering things such as mathematical proof of speed and correctness) to a Computer science magazine.
That way you can always refer back to the article to prove that you were the first to use this algorithm.
This also has the added bonus of letting you put an article on your resume!

What kind of sorting algorithm is it, is it generic, or specific to certain types? And how fast is it?
BakaShinji
BakaShinji
Well I can''t tell you what type of variables it takes yet, but I can tell you it''s extremely fast. In many cases, even while considering Quicksort''s handicaps, it can be exponentially faster. In a lot of real-world applications, it can be hundreds of times faster.

Can you recommend some comp sci magazines and how I should talk to them?
VisualB4BigD
VisualB4BigD
I sure hope you get it up soon, because I really need a fast sort algorithm for my particle engine. I need it to sort about twice as fast as what I use now. That would give me about 6000 more particles per emitter. So please e-mail me if you are interest in having my try it out. I would of course give all credit to you.

I sure hope this world isn''t one big joke, because I don''t get it.
BakaShinji
BakaShinji
Sure I''ll tell you when I get it publicized

Except you might want to mix it along with some other algorithms for something like that though.
Premandrake
Premandrake
If you have really invented a new sorting algorithm that is faster most of the time then anything so far that would be an incredible achievement. Unfortunately the prior art in sorting, is rather large . Chances are, someone has come up with the same idea you have.

If not however, there are a few things to keep in mind.

Comparison only based sorting cannot be faster than O(n logn). You can beat this by specializing the routine into something like bucket sort which is O(n + m) where m is the number of "buckets". I'm guessing this is something like what you've done, but if not, good for you!

Gary

[edited by - premandrake on April 23, 2002 4:23:33 AM]
BakaShinji
BakaShinji
Big-O right? I tried, but my math isn''t that good, and I''m not sure if I can even use big-o for my algorithm... It''s really an oddball

I searched around the net, and as far as I know, there aren''t any similar to mine, or that beat mine.

I''ll probably know for sure when I submit it somewhere though...
BakaShinji
BakaShinji
And ya I know it''d be a big deal if it really is the fastest... At least to profs it would
Premandrake
Premandrake
Yup, that''s Big-O notation. It''s pretty easy to get an idea actually of how fast your algorithm is going to run. Recursive algorithms are a bit harder though. One thing that worries me is you say you''re not sure if Big-O applies. This would probably mean that the algorithm isn''t guaranteed to terminate - which is a bit worrisome .

And just asking a simple question here, does this algorithm trade off memory for speed?
BakaShinji
BakaShinji
Nope it''s not recursive... Can you give me a list of all the variables involved in big-o?

And no it doesn''t trade memory for time
Premandrake
Premandrake
Okay, a very basic primer on Big-O with zero mathematical foundation is as follows:
1) If you have a constant operation it is O(1).

For example: int a = 1; is an O(1) algorithm.

2) If you have a loop based on the input size it is O(n).

For example: for (int i=0; i&ltn i++) d += i; is O(n)

3) Nested loops are are O(n ^ (number of nested loops+1))

For example: for (int i=0; i&ltn i++) for (int j=0; j&ltn j++) d += i*j; is O(n^2)

4) You can get wierd things like O(logn) from things like this:

while (n != 0) n /= 2;

Edit: Fixing < signs

[edited by - premandrake on April 23, 2002 4:50:21 AM]
BakaShinji
BakaShinji
Doh... that still isn''t enough to big-o my algo
BakaShinji
BakaShinji
Wow cool it showed up in Japanese too haha
I''ll look at sourceforge thanks
VisualB4BigD
VisualB4BigD
Could you give us some numbers as too how fast it really sorts. Like say an array of 1000 strings. How fast would that sort on your computer. And what type of computer do you have?

I sure hope this world isn''t one big joke, because I don''t get it.
BakaShinji
BakaShinji
Just tested a few minutes ago
50,000 integers, comparing how many times it can go in 5 seconds.
Quicksort got 9 times, ARaySort 1118 times. I made the test program in visual C++, with MFC. Not the best choice, but I made sure the program doesn''t eat up too much CPU cycles.

-Hewlett Crappard craptop
-AMD k6/2 550 mHz, 196mb ram, using no paging at the moment
-Running Win2k
dalleboy
dalleboy
You could simply add a counter variable to your algorithm and increase it with one each time you do a comparation between two elements. If you have to sort an array with 1000 elements, how many comparations will be done?

Something like this, what will the comparations variable be at the end?


int comparations = 0;
int n = 1000;
int* array = new int[n];

// TODO: fill array with random numbers.

for (int i = 0; i < n; i++)
{
   for (int j = i + 1; j < n; j++)
   {
      comparations++;
      int compresult = comparefunc(array[ i], array[j]);
      if (compresult > 0)
      {
         swap(array[ i], array[j]);
      }
   }
}



[edited by - dalleboy on April 23, 2002 5:24:15 AM]
BakaShinji
BakaShinji
I mean there''s factors that affect its speed that aren''t in big-o

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.