У меня вопрос по алгоритму быстрой сортировки. Я реализую алгоритм быстрой сортировки и играю в него.
Элементы в исходном несортированном массиве являются случайными числами, выбранными из определенного диапазона.
Я нахожу диапазон случайных чисел, влияющих на время работы. Например, время работы 1000 000 случайных чисел, выбранных из диапазона (1 - 2000), занимает 40 секунд. В то время как из диапазона 1 000 000 выбирается число 1 000 000 (1 - 10 000).
Но я не знаю, как это объяснить. В классе мы говорим о том, что значение pivot может влиять на глубину дерева рекурсии.
Для моей реализации последнее значение массива выбрано в качестве основного значения. Я не использую рандомизированную схему для выбора значения разворота.
int partition( vector<int> &vec, int p, int r) {
int x = vec[r];
int i = (p-1);
int j = p;
while(1) {
if (vec[j] <= x){
i = (i+1);
int temp = vec[j];
vec[j] = vec[i];
vec[i] = temp;
}
j=j+1;
if (j==r)
break;
}
int temp = vec[i+1];
vec[i+1] = vec[r];
vec[r] = temp;
return i+1;
}
void quicksort ( vector<int> &vec, int p, int r) {
if (p<r){
int q = partition(vec, p, r);
quicksort(vec, p, q-1);
quicksort(vec, q+1, r);
}
}
void random_generator(int num, int * array) {
srand((unsigned)time(0));
int random_integer;
for(int index=0; index< num; index++){
random_integer = (rand()%10000)+1;
*(array+index) = random_integer;
}
}
int main() {
int array_size = 1000000;
int input_array[array_size];
random_generator(array_size, input_array);
vector<int> vec(input_array, input_array+array_size);
clock_t t1, t2;
t1 = clock();
quicksort(vec, 0, (array_size - 1)); // call quick sort
int length = vec.size();
t2 = clock();
float diff = ((float)t2 - (float)t1);
cout << diff << endl;
cout << diff/CLOCKS_PER_SEC <<endl;
}