Slashdot Mirror

← Back to Stories (view on slashdot.org)

Researching Searching Algorithms?

Posted by Cliff on from the has-this-been-done-before dept.

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?"

2 of 62 comments (clear)

  1. Publish it? by jukal · · Score: 5, Interesting
    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 :)

  2. Re:Funny that this topic came up... by joto · · Score: 5, Interesting
    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.