-2

Given an unsorted vector as source, the goal is to create a sorted copy as fast as possible. There are two possibilities: 1. create a vector copy then sort it 2. or insert each element one after the other, to build the sorted vector incrementally.

Which is theoretically the faster way?

YesThatIsMyName
  • 1,585
  • 3
  • 23
  • 30
Philippe
  • 422
  • 4
  • 7
  • Insertion sort is N^2, so probably will be faster to use merge sort or some NLOGN sort . – sagi Oct 08 '18 at 08:07
  • What you describe with 1. is an "in-place" algorithm. It has nothing to do with faster or not. This is more a problem of memory consumption, than of speed. Every sort algorithm depends on your input vector. Just use the std::sort and you will be fine. See http://www.cplusplus.com/reference/algorithm/sort/ – YesThatIsMyName Oct 08 '18 at 08:18
  • 1
    `std::sort()` has complex `O(N log N)`. Insertion sort (second approach) has complexity `O(N*N)`. If the number of elements is significant, the first option wins on performance. For a small number of elements, YMMV. – Peter Oct 08 '18 at 08:20
  • If those are your only two options (1) is your best worst-case, especially when using something like `std::sort`. And since you're on the subject of "theoretical", if the underlying range of data is sufficiently range-restricted (say integers in 1...100 exclusively), it can be done with something like counting-sort in O(n), which is basically unbeatable in the sorting world. Not that it matters much, since it isn't one of your two options. – WhozCraig Oct 08 '18 at 08:22
  • 1
    This is a legitimate question, why did anyone downvote it? – John Z. Li Oct 08 '18 at 08:24
  • 1
    @JohnZ.Li This is not a legitimate question. Its school homework . – sagi Oct 08 '18 at 08:45
  • 1
    @sagi it boils down to the following: can sort algorithms be made faster if one has some extra memory as large as the data set. – John Z. Li Oct 08 '18 at 08:47

2 Answers2

1

This question has very little to do with C++ specifically (except using the word "vector", which also exists in may other languages). Since this reads like an exercise, I really recommend writing a program to test it out:

1. write a program that builds a vector of random N integers, v1
2. copy the vector to v2, via std::copy
3. time how long it takes to use insertion-sort (option 2 above), using a loop
4. time how long std::sort(v2, v2.begin(), v2.end()) takes

You can time things using different timers, either the old <ctime> header or the newer <chrono> one. See this answer for alternatives.

You should find that, for small sizes of N, the loop from step 3 is faster or equivalent to step 4 - and from a few hundred onward, std::sort becomes better and better. Welcome to asymptotic complexity and big-o notation!

tucuxi
  • 17,561
  • 2
  • 43
  • 74
0

Answers can be found in the following nice conference: in short, this depends on the size of the vector. Hence Peter's comment is the best one. CppCon 2018: Frederic Tingaud “A Little Order: Delving into the STL sorting algorithms”

Philippe
  • 422
  • 4
  • 7