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.

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.

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?

[merdark]

I believe the technique the parent described is a form of hash sort. You must be able to calculate any giving instance of the mapping function M in O(1) time. The situation of infinite memory described is indeed a special case.

A more common and real example of this is sorting a specific range of consecutive integers [a,b]. The function M can simply be M(x)=x-a and is considered a simple hash function. Once all the elements have been hased according to M(x) into some array A, the array A will contain the sorted elements. This clearly takes only O(n) in the worst case.

I beleive it's been proven that any general sort algorithm that does not reley on special conditions on the data or memory has a lower bound of Omega(nlog). Look up decision tree proofs in you favorite algorithm book.

That's not to say that your algorithm is not usefull though. Often people use things like randomized algorithms as they have better average times. So, talk to your professors. They would be happy to explain the specifics of your algorithm to you.

Also, if your library has online journals, you can search those for sorting algorithms. And don't be afriad to show the algorithm to people. If your worried about IP, don't be. Chances are the university already has IP rights to it as your a student. That doesn't mean you can market your algorithm if it turns out to be somethings spectacular. Just talk to your professors, they are the experts!

Google?

[mnordstr]

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

*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.

Re:Check out Perl's source code for more info.

[mikehoskins]

That's not necessarily the case. It depends. C is a very slow language, while Java is incredibly fast, depending on conditions!

I'm mainly referring to Perl's C libraries, BTW.

However, to rebut:

Firstly, Perl is an interpiled/pseudo-compiled language, so it's probably very comparable to Java or Python or PHP or VB for application performance, but YMMV. It also does garbage collection, memory allocation, etc.

Secondly, most of the *wait time* for most apps, whether they are written in Perl or another language, is based on hardware (such as disk I/O), the network, the database, etc.

Thirdly, hardware is very fast today, and programmer time is FAR more expensive than a few measly CPU cycles. I've read anecdotal evidence that a competent Perl programmer is about 50 times more efficient than a competent VB programmer, to solve a given programming task (not counting GUI's or MS-specific stuff)! Also, a programming contest that used to let you use any available language has banned Perl, since it makes solving problems too easy! Since programmer time is a "speed" metric, this point hurts your argument.

Fourthly, Perl's forte is string processing. Heavy string, search, and sort processing is supposedly *MUCH faster* in Perl than in C! This is because of Perl's much faster algorithms.

Fifthly, as a programmer, you're in the driver's seat. What algorithms do you use? How well do you program? Are you using good pre-built modules, or old ones?

Sixthly, there are high-speed math and other high-speed modules for Perl. Do you use those or let Perl convert numbers to/from strings, before/after mathematical operations?

Seventhly, this is a old, moot argument, most of the time, these days. Unless something is "too slow" to be of practical use, it isn't. Go back to the six points above this one, no matter what language you use, and think through your problem.

Ergo, nope, Perl is most definitely NOT SLOW, until you've exhausted the above, at least. The same is true for any language, including assembly.

Besides, execution time is no longer important to most people, for good reason. Other factors, these days are higher on the list, as they should be.

Do you have specific examples? Where was it slow? Did you profile the functions in your code and then ask for help, once you couldn't find a reasonable solution? Did you try somebody else's pre-built module? What version of Perl did you use? Did you have hardware that was too small to load up the environment? Did you try Perl CGI without mod-Perl or Fast CGI, etc.? How exhaustive were you? (This and the above are on the short list, actually.)

Maybe it's me, but as a person who programs almost daily in Perl, I find that it's *really, realy, really fast*, most of the time. When it's not, I'm waiting on some silly Access database (not Oracle, MySQL, or PostgreSQL), or some other resource, the rest of the time. For example, when I load millions of records, on inferior hardware, from a flat file, in Perl, it usually takes a fraction of a second, unless I print it to the screen, or load straight into a database. How much faster should I make it? (I could, but what a waste of time, unless I need to load billions of records? Of course, we're now talking about 64-bit equipment.)

Perl has perhaps the largest organized community of developers that are very willing to help you on this.

I don't intend to start a language war, but have some facts before trolling, please. Any language I could have chosen will have people for and against it. If I would have said "Python" or "PHP "or "Java" or "VB" or even "C++," I might have gotten this response.