CODEWITHSUNDEEP
c++
user3617449
user3617449

Reputation: 103

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

Upvotes: 10

Views: 25072

Answers (6)

Fenil Mehta
Fenil Mehta

Reputation: 1

Sorting

In case you want to know about the fastest sorting technique for integer values in a vector then I would suggest you to refer the following link: https://github.com/fenilgmehta/Fastest-Integer-Sort

It uses radix sort and counting sort for large arrays and merge sort along with insertion sort for small arrays. According to statistics, this sorting algorithm is way faster than C++ std::sort for integral values.

It is 6 times faster than C++ STL std::sort for "int64_t array[10000000]"

Searching

If you want to know whether a particular value is present in the vector or not, then you should use binary_search(...)

If you want to know the exact location of an element, then use lower_bound(...) and upper_bound(...)

Upvotes: 0

Deduplicator
Deduplicator

Reputation: 45654

For amortised O(1) access times, use a [std::unordered_map], maybe using a custom hash for best effects.
Sorting seems to be unneccessary extra work.

Upvotes: 3

Dimitrios Bouzas
Dimitrios Bouzas

Reputation: 42899

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

Upvotes: 17

Daniel Heilper
Daniel Heilper

Reputation: 1250

if your elements are of integer you should use bucket sort algorithm which run at O(N) time instead of O(nlogn) average case as with qsort [http://en.wikipedia.org/wiki/Bucket_sort]

Upvotes: 0

Thomas Matthews
Thomas Matthews

Reputation: 57678

Searching and Sorting efficiency is highly dependent on the type of data, the ordering of the raw data, and the quantity of the data.

For example, for small sorted data sets, a linear search may be faster than a binary search; or the time differences between the two is negligible.

Some sort algorithms will perform horribly on inversely ordered data, such a binary tree sort. Data that does not have much variation may cause a high degree of collisions on hash algorithms.

Perhaps you need to answer the bigger question: Is search or sorting the execution bottleneck in my program? Profile and find out.

Upvotes: 2

Slava
Slava

Reputation: 44238

If you need the fastest or the best sorting algorithm... There is no such one. At least it haven't been found yet. There are algorithms that provide better results for different data, there are algorithms that provide good results for most of data. You either need to analyze your data and find the best one for your case or use generic algo like std::sort and expect it to provide good results but not the best.

Upvotes: 1

Related Questions