user3617449 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)

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

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

Answer Source

  • 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 enter image description here complexity). However, quick-sort has quadratic worst-case performance (i.e., enter image description here). 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):

enter image description here

  • 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., enter image description here). 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 enter image description here 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.

enter image description here

Bottom Line:

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