void quick_sort(int * a, int left, int right, int & count) {
int key = a[ (left + right) / 2 ];
int i = left;
int j = right;
do {
while (++count, a[i] < key) ++i;
while (++count, key < a[j]) --j;
if (i <= j) {
swap(a[i], a[j]);
++i, --j;
}
} while (i <= j);
if (left < j) quick_sort(a, left, j, count);
if (i < right) quick_sort(a, i, right, count);
}
Напишите программу, которая для заданного N формирует перестановку чисел от 1 до N чтобы count (количество перестановок) был максимальным. Является ли найденный вариант перестановки также худшим случаем в отношении глубины рекурсии?
Б>void quick_sort(int * a, int left, int right, int & count) {
Б> int key = a[ (left + right) / 2 ];
Б> int i = left;
Б> int j = right;
Б> do {
Б> while (++count, a[i] < key) ++i;
Б> while (++count, key < a[j]) --j;
Б> if (i <= j) {
Б> swap(a[i], a[j]);
Б> ++i, --j;
Б> }
Б> } while (i <= j);
Б> if (left < j) quick_sort(a, left, j, count);
Б> if (i < right) quick_sort(a, i, right, count);
Б>}
Б>
Б>Напишите программу, которая для заданного N формирует перестановку чисел от 1 до N чтобы count (количество перестановок) был максимальным. Является ли найденный вариант перестановки также худшим случаем в отношении глубины рекурсии?
Б>Навеяно/взято с http://dxdy.ru/topic98700.html
Точно перестановок?
Приведенная реализация считает число сравнений ...
Перестановки, на которых алгоритм производит максимум сравнений приводят и к максимальной глубине рекурсии.
Единственный момент, на который нужно обратить внимание — перестановка {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;
}
}
Б>void quick_sort(int * a, int left, int right, int & count) {
Б> int key = a[ (left + right) / 2 ];
Б> int i = left;
Б> int j = right;
Б> do {
Б> while (++count, a[i] < key) ++i;
Б> while (++count, key < a[j]) --j;
Б> if (i <= j) {
Б> swap(a[i], a[j]);
Б> ++i, --j;
Б> }
Б> } while (i <= j);
Б> if (left < j) quick_sort(a, left, j, count);
Б> if (i < right) quick_sort(a, i, right, count);
Б>}
Б>
Б>Напишите программу, которая для заданного N формирует перестановку чисел от 1 до N чтобы count (количество перестановок) был максимальным. Является ли найденный вариант перестановки также худшим случаем в отношении глубины рекурсии?
Чтобы максимально углубить рекурсию, нужно, чтобы опорный элемент был минимальным или максимальным в текущем подмассиве.
Тогда результат разбиения [L..R] — будет [L..L], [L+1..R] или [L..R-1], [R..R], и мы получим линейную глубину.
Поскольку опорный элемент берётся из середины, то массив можно нагенерировать, выполнив обход двоичного дерева вглубь.
void make_deepest(DATA* a, int L, int R, DATA& t) {
int M = (L+R)/2;
a[M] = t++;
if (L<M) make_deepest(a, L, M-1, t);
if (M<R) make_deepest(a, M+1, R, t);
}
void make_deepest(DATA* a, int N) { DATA t = 0; make_deepest(a, 0, N-1, t); }
Чтобы максимизировать count — в твоей трактовке кода, нужно, чтобы количество перестановок было минимальным. Ибо он считает количество пропусков.
Если опорный элемент минимальный, то цикл do-while будет выглядеть так
// итерация 0
count += 0; i = L;
count += (R-M); j = M;
swap(a[0], a[M]); i = L+1; j = M-1;
// итерация 1
count += 0; i = L+1;
count += (M-1-L); j = L;
итого, count += R-L-1.
Таки да: стратегия правильная.
А вот чтобы сделать как можно больше swap-ов... Надо подумать.
Инвариант функции — это то, что { a[i] | i <- [L..R] } = {L..R}
Пусть опорное значение для разбиения, взятое из ячейки M=(L+R)/2 или какой угодно другой, равно Q.
Поскольку обмены выполняются только тогда, когда a[i]>=Q и a[j]<=Q, то максимальное количество обменов равно min(Q-L,R-Q)+1
Дальше получается формула для динамического программирования
MaxSwaps(R-L) = S(n) = ...
S(0) = 0 — нет данных, нет обменов
S(1) = 0 — нет альтернатив, нет обменов
S(2) = 1 — возможно, один раз придётся упорядочить
S(n) = max (min(q,n-q)+1 + S(q)+S(n-q-1)) | q <- [0..n]
т.е. выполняем обмены при разбиении и уходим в рекурсию по обеим веткам
(вроде, ничего не напутал?)
и прослеживается тенденция: желательно, чтобы опорной точкой была именно медиана.
S(n) = m+1 + 2*S(m), где m = floor(n/2)
Таким образом, получается, — либо мы опорным значением выбираем минимум или максимум, — максимизируем глубину и сравнения; либо выбираем медиану, — максимизируем обмены.
В твоём коде count подсчитывает сравнения, — я уже сказал выше.
Перекуём баги на фичи!
