Сообщение Re: Худший случай быстрой сортировки от 16.09.2015 17:41
Изменено 17.09.2015 8:54 NotImplemented
> Здравствуйте, Буравчик, Вы писали:
Перестановки, на которых алгоритм производит максимум сравнений приводят и к максимальной глубине рекурсии.
Единственный момент, на который нужно обратить внимание — перестановка {2,1} дает меньше сравнений, чем {1,2}. Поэтому обменяем 1 и 2 в результирующей перестановке.
Перестановки, на которых алгоритм производит максимум сравнений приводят и к максимальной глубине рекурсии.
Единственный момент, на который нужно обратить внимание — перестановка {2,1} дает меньше сравнений, чем {1,2}. Поэтому обменяем 1 и 2 в результирующей перестановке.
vector<int> find_adversary(const int n)
{
vector<int> data(n);
vector<pair<int, int> > pairs;
// Maintain original positions.
for(int i = 0; i < n; ++i)
data[i] = i;
// At each step data[k/2] contains initial position after reverse (n-(k+1)) qsort applications.
// Set it to maximal value.
for(int k = n - 1; k >= 0; --k)
{
pairs.push_back(make_pair(k, data[k/2]));
swap(data[k/2], data[k]);
}
vector<int> result(n);
for(int i = 0; i < n; ++i)
{
result[pairs[i].second] = pairs[i].first + 1;
}
// Just swap 1 and 2 in result permutation due to the fact that {1, 2} gives 3 and {2, 1} gives 2 comparisons.
swap(*find(result.begin(), result.end(), 1), *find(result.begin(), result.end(), 2));
return result;
}
void quick_sort(vector<int>& data, int left, int right, int & count) {
int key = data[ (left + right) / 2 ];
int i = left;
int j = right;
do {
while (++count, data[i] < key) ++i;
while (++count, key < data[j]) --j;
if (i <= j) {
swap(data[i], data[j]);
++i, --j;
}
} while (i <= j);
if (left < j) quick_sort(data, left, j, count);
if (i < right) quick_sort(data, i, right, count);
}
int main()
{
const int answers[] = {3, 6, 12, 19, 27, 36, 46, 57, 69, 82};
for(int i = 0; i < sizeof(answers)/ sizeof(answers[0]); ++i)
{
const int n = i + 2;
vector<int> adversary = find_adversary(n);
int count = 0;
quick_sort(adversary, 0, n-1, count);
if (count != answers[i])
cout << "Case #" << i << ": FAILED!" << " Expected: " << answers[i] << " Received: " << count << endl;
else
cout << "Case #" << i << ": PASSED!" << endl;
}
}
Re: Худший случай быстрой сортировки
> Здравствуйте, Буравчик, Вы писали:
Перестановки, на которых алгоритм производит максимум сравнений приводят и к максимальной глубине рекурсии.
Единственный момент, на который нужно обратить внимание — перестановка {2,1} дает меньше сравнений, чем {1,2}.
Поэтому обменяем 1 и 2 в результирующей перестановке.
Немного улучшил решение, убрал лишний массив.
E-olymp submission
Перестановки, на которых алгоритм производит максимум сравнений приводят и к максимальной глубине рекурсии.
Единственный момент, на который нужно обратить внимание — перестановка {2,1} дает меньше сравнений, чем {1,2}.
Поэтому обменяем 1 и 2 в результирующей перестановке.
Немного улучшил решение, убрал лишний массив.
E-olymp submission
vector<int> find_adversary(const int n)
{
vector<int> data(n);
for(int i = 0; i < n; ++i)
data[i] = i;
vector<int> result(n);
for(int k = n - 1; k >= 0; --k)
{
result[data[k/2]] = k+1;
swap(data[k/2], data[k]);
}
swap(*find(result.begin(), result.end(), 1), *find(result.begin(), result.end(), 2));
return result;
}
void quick_sort(vector<int>& data, int left, int right, int & count) {
int key = data[ (left + right) / 2 ];
int i = left;
int j = right;
do {
while (++count, data[i] < key) ++i;
while (++count, key < data[j]) --j;
if (i <= j) {
swap(data[i], data[j]);
++i, --j;
}
} while (i <= j);
if (left < j) quick_sort(data, left, j, count);
if (i < right) quick_sort(data, i, right, count);
}
int main()
{
const int answers[] = {3, 6, 12, 19, 27, 36, 46, 57, 69, 82};
for(int i = 0; i < sizeof(answers)/ sizeof(answers[0]); ++i)
{
const int n = i + 2;
vector<int> adversary = find_adversary(n);
int count = 0;
quick_sort(adversary, 0, n-1, count);
if (count != answers[i])
cout << "Case #" << i << ": FAILED!" << " Expected: " << answers[i] << " Received: " << count << endl;
else
cout << "Case #" << i << ": PASSED!" << endl;
}
}