Fastest way to search and sort vectors

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

Answer 1

---

• 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:

  1. The number of elements/objects (see chart below).
  2. 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.