choosing the best search algorithm

[sporx]

Hi, ive been doing some research trying to figure out when different search algorithms are appropriate to use. Googling around, im really not coming up with much on the topic. I can find the big O of each, and the basic structure, but I cant really find a reason why some of the slower ones, like for instance bubble sort even exist when you have sorts like quick sort that perform better in most situations. I was wondering if anyone could either point me in the right direction, or help give me break down of when its proper to use each search function. maybe specific questions to answer before deciding on which would best suit your needs?

thanks!
-sporx

[imi]

http://en.wikipedia.org/wiki/Sorting_algorithm

Ciao, Imi.

[Bazzy]

Are you looking for search algorithms or sorting algorithms?
btw bubble sort is the easiest sorting algorithm to think of and it's only used in education

[sporx]

thanks for the replies=]
I am looking for an educated way to choose the proper search algorthim (quick sort, bubble sort, shell sort, etc) in any given situation.
I would like to know how to properly choose between your options in sorting data in a given circumstance
reading around the best i can tell is that the deciding factors are big O, ease of use (some are way harder to properly code), amount of data entries..

[Bazzy]

quick sort, bubble sort, shell sort are sorting algorithms, not searching algorithms
The best sorting algorithm depends on what you know about the data you'll have to sort ( number of items to sort, distribution of the values, etc )

[kempofighter]

As bazzy has pointed out the best case / worst case scenarios depend too much on the data structure itself. Therefore there is not any sort that is guaranteed to work best for all cases of input data. You have to compromise and figure out which sort is best most of the time or consider the types of data that you will have to sort within your program first.

In short, if you are using c++ use std::sort or std::stable_sort most of the time unless you can prove that it isn't working efficiently enough or use one of the containers such as std::set, std::map that keeps things sorted by the key as you insert items. std::list has its own sort as a member function. When dealing with std containers prefer member functions over algorithms when available.

[imi]

I am looking for an educated way to choose the proper search algorthim (quick sort, bubble sort, shell sort, etc) in any given situation.

You can extract some information from the table under "Comparison of algorithms" in wikipedia. As you see, some algorithms use only constant memory, but are not faster than O(nlogn). Some algorithms are stable (means: Two equivalent elements never get swaped in order), which is just necessary for some applications.

All algorithms faster than O(nlogn) need additional information or properties about the unsorted data. If you can't provide this information, you can't use them. Period. ;).

What's not nicely visible in the table is, that some algorithms need a quite large and constant setup time (e.g. because they need to prepare an array or just need to allocate tons of memory), which make them suboptimal in practice when you sorting a very small amount of data. For this reason, modern implementations use a threshold size, e.g. "everything less than 32 items") under which they use different algorithms (like insertion or bublle sort).

Ciao, Imi.

[ramKrushna]

merge sort is one of the best algorithm can be used


http://en.wikipedia.org/wiki/Merge_sort

[paritosh]

if you have an already sorted list , then binary search algorithm is best