2

From time to time have I come across manually implemented sort and/or search algorithms, instead of using language implemented algorithms. Most source code I've been looking into is written in Java, C# or PHP - but I'd guess this phenomenon is language agnostic.

Regarding regular data structures such as lists; Why and where do you implement your own algorithm? Ideological reasons? More memory efficient? Can't stand the idea of using built-in features? Java preferably uses mergesort (in Collections.sort()), which has some overhead when you compare it to quicksort as an example. If you have a favorite which you use on a regular basis for doing common tasks, you're more than welcome to submit it in your language of choice!

Improve this question

4 Answers 4

Reset to default
6
  • Not every sort algorithm is implemented by the standard library.
  • Not every language supports generic data types/containers
  • Sometimes you need to switch between sorting algorithms depending on data-size
  • Tweaking the algorithm for a particular set of input is easier
  • To measure processor speed
  • Coursework
  • Just for fun

These are just some of the reasons ...

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Of course. I was more interested in different solutions of the community. Rephrased the question...
3

Bogosort:

while (!is_sorted(array)) {
    randomly_shuffle(array);
}

Expected running time: O(n!)

:)

Improve this answer

2 Comments

For optimal performance, be sure to use an evenly-distributed shuffle, such as Fisher-Yates.
Good idea. Ideally you'd want a source of true randomness, such as the voltage across a noisy diode or the text from the CodeSOD articles on www.thedailywtf.com.
1

In C++ you can have a container with an array inside that is only searched by methods of the container. You can use some library implementation but then you'll have to provide a comparator class and that's the same amount of code as simply writing a for() loop. Why produce a new entity (comparator class) for such case?

Improve this answer

1 Comment

This is the kind of answer I was looking for!
1

Built in language implementations will be normally be faster, but only if you are sorting/searching in a standard way. As soon as you do anything a little unusual, be it the way the key is interpreted, dealing with multiple pointers, hooking into a different enviroment and so on you can better performance by tweaking the basic routines to match your exact requirements.

For instance, I needed to keep three large (huge) data sets sorted on the same key, so I had to go back to source and alter the C quick sort code to move elements on three distinct arrays of data.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.