user3617449 - 4 years ago 172
C++ Question

# Fastest way to search and sort vectors

I'm doing a project in which i need to insert data into vectors sort it and search it ...

i need fastest possible algorithms for sort and search ... i've been searching and found out that std::sort is basically quicksort which is one of the fastest sorts but i cant figure out which search algorithm is the best ? binarysearch?? can u help me with it? tnx ... So i've got 3 methods:

``````void addToVector(Obj o)
{
fvector.push_back(o);
}

void sortVector()
{
sort(fvector.begin(), fvector().end());
}

Obj* search(string& bla)
{
//i would write binary search here
return binarysearch(..);
}
``````

• Quick-sort is one of the fastest sorting methods.

Answer: Not quite. In general it holds (i.e., in the average case quick-sort is of complexity). However, quick-sort has quadratic worst-case performance (i.e., ). Furthermore, for a small number of inputs (e.g., if you have a `std::vector` with a small numbers of elements) sorting with quick-sort tends to achieve worst performance than other sorting algorithms that are considered "slower" (see chart below):

• I can't figure out which searching algorithm is the best. Is it binary-search?

Answer: Binary search has the same average and worst case performance (i.e., ). Also have in mind that binary-search requires that the container should be arranged in ascending or descending order. However, whether is better than other searching methods (e.g., linear search which has time complexity) depends on a number of factors. Some of them are:

1. The number of elements/objects (see chart below).
2. The type of elements/objects.

Bottom Line:

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download