クイックソート3ウェイパーティションが遅すぎる

Question

私はクイックソート3ウェイパーティションを使用していますが、ベクトルサイズが10000を超えると遅すぎることが判明しています。 私は間違っていますか？私を案内してください！助けを歓迎します 答えは2.2秒未満で計算する必要があります。一見

#include <iostream> 
#include <vector> 
#include <cstdlib> 
#include <algorithm> 

using std::vector; 
using std::swap; 

void print(vector<int> v) 
{ 
    for(int i = 0; i < v.size(); i++) std::cout << v[i] << " "; 
    std::cout << std::endl; 
} 

void partition2(vector<int> &a, int l, int r, int &i, int &j) { 
    int k; 
    int middle=(l+r)/2; 
    /*Selecting pivot as median of low, high and middle*/ 
    if(((a[l]<=a[middle]) && (a[middle]<=a[r])) || ((a[r]<=a[middle]) && (a[middle]<=a[l]))) 
     k=middle; 
    else if(((a[middle]<=a[l]) && (a[l]<=a[r])) || ((a[r]<=a[l]) && (a[l]<=a[middle]))) 
     k=l; 
    else if(((a[middle]<=a[r]) && (a[r]<=a[l])) || ((a[l]<=a[r]) && (a[r]<=a[middle]))) 
     k=r; 

    swap(a[l], a[k]); 
    //print(a); 

    int low_value = a[l]; 
    int index_low = l; 
    int index_high = l; 
    int counter=l; 
    for (int i = l + 1; i <= r; i++) { 
    if (a[i] < low_value) { 
     swap(a[i], a[index_low]); 
     counter++; 
     low_value=a[l]; 
    } 
    else if(a[i]==low_value) 
    { 
     index_high++; 
     swap(a[i], a[index_high]);  
    } 
    //print(a); 
    } 

    i=counter; 
    j=index_high; 
    //swap(a[l], a[j]); 
    //return j; 
} 

void randomized_quick_sort(vector<int> &a, int l, int r) { 
    if (l >= r) { 
    return; 
    } 

    int i,j; 
    partition2(a, l, r, i, j); 

    randomized_quick_sort(a, l, i-1); 
    randomized_quick_sort(a, j+1, r); 
} 

int main() { 
    int n; 
    std::cin >> n; 
    //while(1){ 
    //n=100+rand()%99999; 
    //std::cout<<n<<std::endl; 
    vector<int> a(n); 
    for (size_t i = 0; i < a.size(); ++i) { 
    std::cin >> a[i]; 
    //a[i]=1+rand()%99999999; 
    } 
    randomized_quick_sort(a, 0, a.size() - 1); 
    for (size_t i = 0; i < a.size(); ++i) { 
    std::cout << a[i] << ' '; 
    } 
    //std::cout<<"Pass\n"; 
    //} 
    return 0; 
} 

Answer 1

すべてが正しいです。しかし、あまりにも多くの比較操作が存在する可能性があります。このオプションを試してみてください。これは平均して1.6秒間コンピュータ上で動作します。

#include <stdlib.h> 
#include <stdio.h> 
#include <iostream> 
#include <vector> 
#include <ctime> 
#include <random> 
#include <chrono> 
#include <iomanip> 

using namespace std; 
using namespace std::chrono; 

//======= quick_sort =======// 
template<typename T> 
int partition(vector<T>& numbers, const int& left, const int& right) 
{ 
    swap(numbers[left], numbers[left + (right - left)/2]); 
    T mid = numbers[left]; 
    int i(left + 1), j(right); 

    while (i <= j) 
    { 
     while (i <= j && numbers[i] <= mid) i++; 
     while (i <= j && numbers[j] > mid) j--; 
     if (i < j) swap(numbers[i], numbers[j]); 
    } 

    swap(numbers[i - 1], numbers[left]); 
    return i - 1; 
} 

template<typename T> 
void quick_sort_rec(vector<T>& numbers, const int& left, const int& right) 
{ 
    if (left >= right) return; 

    int p = partition(numbers, left, right); 
    quick_sort_rec(numbers, left , p - 1); 
    quick_sort_rec(numbers, p + 1 , right); 
} 
//=========================// 


template<typename T> 
T random_T(long min, long max) 
{ 
    return (T)min + static_cast<T>(rand())/(static_cast<T>(RAND_MAX/((T)(max - min)))); 
} 

template<typename T> 
float time_func(void (*f)(vector<T>&, const int&, const int&), vector<T>& a) 
{ 
    high_resolution_clock::time_point t1 = high_resolution_clock::now(); 
    f(a, 0, a.size() - 1); 
    high_resolution_clock::time_point t2 = high_resolution_clock::now(); 

    return 1000.0 * (duration_cast<microseconds>(t2 - t1).count())/(float)(CLOCKS_PER_SEC); /// CLOCKS_PER_SEC; 
} 

int main() 
{ 
    srand((unsigned)(777)); 
    vector<int> a; 

    for (int i = 0; i < 10000; i++) 
    { 
     a.push_back(random_T<int>(0, 1000)); 
    } 

    cout << setprecision(10) << "quick sort rec = " << time_func(quick_sort_rec, a) << endl; 
    return 0; 
} 

Answer 2

その後、ピボット、私は

int main(){ 
    vector<int> a = {2, 1, 1, 9, 5, 3, 4, 2, 7}; 
    int i, j; 
    partition2(a, 0, a.size() - 1, i, j); 
    for (auto i : a) 
     cout << i << ' '; 
    cout << '\n'; 
    return 0; 
} 

をパーティション2テストするには、次のコードを実行し、パーティション2は、ピボットとして、低中高の中央値を選択した場合の結果は

1 1 5 9 2 3 4 2 7 

です5とする必要があります。結果は次のようになります。

2 1 1 3 4 2 5 9 7 

はその後、私はコードが配列の最小値を検索し、配列の先頭に移動しようということのようだコード

if (a[i] < low_value) { 
    swap(a[i], a[index_low]); 
    counter++; 
    low_value=a[l]; 
} 
else if(a[i]==low_value) 
{ 
    index_high++; 
    swap(a[i], a[index_high]);  
} 

をご確認ください。クイックソートの代わりに選択ソートを行っているようです。入力サイズが大きいときになぜそれが遅いのかを説明します。