diff options
author | Marc Mutz <marc.mutz@kdab.com> | 2013-09-11 23:10:18 +0200 |
---|---|---|
committer | The Qt Project <gerrit-noreply@qt-project.org> | 2013-09-12 14:12:30 +0200 |
commit | 880b614c8ffd530251b9383e085ba094a1edbca8 (patch) | |
tree | 21a7e4e0e046e91f3687690b19c5474fbd8b94b8 /src | |
parent | 1ec37184329afa1c76141a3663f6adb5536fd051 (diff) |
QtConcurrent: use nth_element to calculate the (correct) median
Sorting is O(NlogN) complexity, while nth_element is linear.
Also remove the errornous +1 when calculating the median position.
Change-Id: Ib39085b59a6c5d15a3a940b1ce3377080340bc09
Reviewed-by: Olivier Goffart <ogoffart@woboq.com>
Diffstat (limited to 'src')
-rw-r--r-- | src/concurrent/qtconcurrentmedian.h | 7 |
1 files changed, 4 insertions, 3 deletions
diff --git a/src/concurrent/qtconcurrentmedian.h b/src/concurrent/qtconcurrentmedian.h index 9079393388..b39b3ed32b 100644 --- a/src/concurrent/qtconcurrentmedian.h +++ b/src/concurrent/qtconcurrentmedian.h @@ -102,9 +102,10 @@ public: { if (dirty) { dirty = false; - QVector<T> sorted = values; - std::sort(sorted.begin(), sorted.end()); - currentMedian = sorted.at(bufferSize / 2 + 1); + QVector<T> copy = values; + typename QVector<T>::iterator begin = copy.begin(), mid = copy.begin() + bufferSize/2, end = copy.end(); + std::nth_element(begin, mid, end); + currentMedian = *mid; } return currentMedian; } |