user3617449 - 2 years ago 114

C++ Question

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(..);

}

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

I've been searching and found out that`std::sort`

is basically quicksort.

Answer:Not quite. Most implementations use a hybrid algorithm like introsort, which combines quick-sort, heap-sort and insertion sort.

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:

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

Bottom Line:

Usually looking for the "fastest" algorithm denotes premature optimization and according to one of the "great ones" (

Premature optimization is the root of all evil - Donald Knuth). The "fastest", as I hope it has been clearly shown, depends on quite a number of factors.Use

`std::sort`

to sort your`std::vector`

.After sorting your

`std::vector`

use`std::binary_search`

to find out whether a certain element exists in your`std::vector`

or use`std::lower_bound`

or`std::upper_bound`

to find and get an element from your`std::vector`

.

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