Researching Searching Algorithms?

NiN3x asks: "I have recently written a sorting algorithm that can be close to four times as fast as quicksort and never much slower. I was wondering if there are lots of sorting algorithms like this out there. I don't think I could be the only one that has thought of something like this. I am only in my second year of computer science, so I don't know a lot about these things. I have tried searching the net and can't find anything. My algorithm is NOT an inplace sorting algorithm. Can anyone point me to some sources for this type of thing?"

Comments

Bible

[Anonymous Coward]

Knuth, Donald E., The Art of Computer Programming Vol 3.

Publish it?

[jukal]

I have recently written a sorting algorithm that can be close to four times as fast as quicksort and never much slower

Is there some reason why you cannot publish it here for a review? A basic C reference cannot be very many lines? This way people could give real input for you. I don't believe you have much to lose. If you do, attach your favorite license to it :)

Check out Perl's source code for more info.

[mikehoskins]

They've used modern algorithms extensively throughout, since Perl is geared mostly to string (scalar) processing.

If your algorithm is general-purpose and happens to be faster, why not GPL/LGPL/BSD it and contribute to Perl's, Python's, and PHP's sorting and searching code?

Funny that this topic came up...

[ed1park]

As I was just studying algorithms last night. The following is considered one of the most definitive books on algorithms.

Art of Computer Programming, Volume 3: Sorting and Searching by Donald Knuth

http://www.amazon.com/exec/obidos/tg/detail/-/02 01 896850/qid=1035291515/sr=8-3/ref=sr_8_3/002-899931 0-6640041?v=glance&n=507846

And since you are a student, go show it to a CS professor for immediate feedback. My guess will be that you haven't properly analyzed the O(n) performance.

Re:Funny that this topic came up...

[joto]

Well, he doesn't have to. Because he didn't claim an asymptotically better algorithm. He claimed to have an algorithm better than quicksort (by a factor of 4). This can still mean an O(nlogn) algorithm.

My guess, is that it really isn't. There are many algorithms that are faster than quicksort for smaller inputs. For less than 100 elements, insertion sort wins (hands down). For less than "really more than you usually need to sort, but not really extreme values", shell-sort usually wins.

Also, there are lots of algorithms that are faster than O(nlogn) when you have more information than that given to you by &lt:. One example would be bucket-sort.

Personally, I couldn't care less. The chances of a second-year student inventing a better sorting algorithm that isn't already published somewhere is nada. That doesn't mean that he is not smart, and that his algorithm is stupid. It *is* probably better than quicksort for the test-cases he has tested it on (and maybe for many more). What it means is that the field of sorting is so well-studied that it is very unlikely to get real contributions from somebody without at least two PhD's in mathematics these days.

Re:Funny that this topic came up...

[Twylite]

The interesting thing about O(nlogn) versus O(n) or O(whatever-you-want) is that an "operation" is not often the same between algorithms.

So an O(nlogn) implementation is still faster than an O(n) implementation when the input set is less than 1,000,000 items and the latter implementation requires 6 times the time per operation compares to the former.

So while it is unlikely that someone without a vast theoretical background will discover a better algorithm for all cases (or even the extreme cases), as you point out; there is a significantly greater liklihood that he could have discovered an algorithm which provides improvement for data sets which are commonly used in certain - even many - fields. Without having multiple doctorates.

Sorting in general is a well-studied field; but as the application of computers grows, the need for less general sorting grows as well. Many data structures and algorithms are not considered "sorted" because they are partitioned, or implicitly ordered, yet they make use of sorting theory.

Re-Searching Searching?

[Eagle7]

I take it your algorithm is redundant?

Algorithm resources

[Twylite]

The definitive online resource for algorithms is NISTS's Dictionary of Algorithms and Data Structures. There is a list of algorithm resources, and you can also find some free e-books using The Assayer.

In print you should be looking for "Introduction to Algorithms, 2nd edition". It is the bible of the field. Other excellent candidates are "Data Structures and Algorithms" ( / in Java / in C).

Google will also tell you to look here, here and here.

Apples and Oranges?

[Bazzargh]

Quicksort is an in-place sorting algorithm. If you're not sorting in place it's well known that you can do better. Telling us the sort isn't in-place means your either doing an external sort (which isnt where you'd use quicksort) or you're breaking the other condition - the constant memory limit. I'm guessing you're doing the latter - trading time for space - and its /well known/ that better sorts exist in this case.

The easy way to show that faster sorts exist is to demonstrate absurd limit case of a tradeoff of space for speed. Consider you have an unlimited amount of memory available for your sort results, and that you are sorting a finite number of keys N for which a mapping M(n) exists to the positive integers. Then, since there can be at most N duplicates of any given key, scanning the data once and placing each key n(i) in memory address N*M(n(i))+i sorts all the data. This is O(N), and pretty much optimal.

If you know there are no duplicates and the keys fill a known range this can be practical.

A good place to start reading about other sorting algorithms is here: http://www.nist.gov/dads/HTML/sort.html

Re:Apples and Oranges?

[mr3038]

The easy way to show that faster sorts exist is to demonstrate absurd limit case of a tradeoff of space for speed. Consider you have an unlimited amount of memory available for your sort results, and that you are sorting a finite number of keys N for which a mapping M(n) exists to the positive integers. Then, since there can be at most N duplicates of any given key, scanning the data once and placing each key n(i) in memory address N*M(n(i))+i sorts all the data. This is O(N), and pretty much optimal.

Yeah, the sorting is O(N) but reading the result is O(N^2) and without knowing the result the sorting itself doesn't do much good. That's because you need N^2 of memory and in worst case you have to do linear scan through the whole memory. If you think about sorting it should be pretty clear that O(n log n) is best you can get if you have no information about the data and it's uniformly distributed. IIRC worst case for heap sort is O(n log n) and worst case for quicksort is O(n^2) so if you don't need in-place sorting you should use for example heap sorting. If you don't have many items to sort just do insertion sort because it has least overhead.

Proper Analysis is Key

[photon317]

There are lots of algorithms out there that seem to be multiples faster than quicksort in daily use. The problem is when you formally analyze them, you find out their not gauranteed to be faster, and could in fact be horribly slower. If you run it enough times against various wierd data, you'll probably hit one of these slow runs yourself. I can only guess because you haven't mentioned anything about the algorithm or shown any sample code. Read up on how to analyze your code for O() notation and figure out what the real worst case is mathematically.

Google?

[mnordstr]

I assume you have checked these out:
http://directory.google.com/Top/Computers/Algorith ms/Sorting_and_Searching/

Well, post it.

[Tom7]

Post your algorithm, then!

There are many implementations of quicksort-like sorts, but when done well, quicksort is pretty damn fast. For instance, if you're measuring against a version that doesn't special case arrays of size 3, 4, and maybe even bigger, then it will run many times slower than a tuned version. You won't be able to beat quicksort (with proper pivot-picking) asymptotically, so there won't be any ground-breaking result here, but it's probably possible to beat its constant factors (which may be practically useful)... and there are probably many people here who'd be willing to look at the algorithm if you posted it.

*sigh*

[SomeGuyFromCA]

#1, Google and see if someone else has already worked on the algorithm. "Nothing new under the sun".

#2, if that gives you no results, post the code or at least pseudo-code so we can comment. Not "I have a new miracle development that could be revolutionary; please comment on it with no clue as to exactly what it is or how it works."

#3, talk to a CS professor. You should know plenty of them.

And the obligatory link - http://www.cs.ubc.ca/spider/harrison/Java/sorting- demo.html.

amazing

[larry bagina]

What's the deal with Ask Slashdot lately?

"I'm a 2nd year cs student, and I discovered an unknown searching algorithm. I won't provide any details, though"

"I'm not that good at math, but I just invented a new unbreakable multipad encryption. I won't provide any details, though"

"During my lunch break, I used a couple coat hangers, some aluminum foil, a 3 hole punch, a spare xeon-argon laser, and 32oz of diet pepsi to create my own home-brewed cold fusion reactor."

Can you identify the PhysicsGenius troll from the Ask Slashdot question?

And people complain about what gets through the US Patent Office!

Re:amazing

[quintessent]

Dear Slashdot,

I just finished Kindergarten, where we learned our ABC's, and I've invented an alphabet that can be read 7 times as fast, with only one third the effort. Why didn't some PhD come up with this before? Oh well. I don't remember what my question was, but just post this, ok?