2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Худший случай для Быстрой сортировки
Сообщение19.06.2015, 22:08 


10/05/13
251
Здарова ребята!
Сидел июньским вечерком и решал задачки по программированию, для тренировки мозга, да и пальцы размять ;).
И вдруг, начались сложности с задачей. Задачка вроде простая, дан конкретный код быстрой сортировки:
Код:
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);
}

Надо найти перестановку элементов от $1$ до $N$, такую,
что на ней значение переменной count после работы сортировки будет максимальной.

Ясно что для быстрой сортировки, худший случай, когда она в качестве опорного элемента выбирает максимальный в подмассиве, который сортирует, в такой случае глубина рекурсии будет N. Но, я считаю, что одной теоретической информации о сортировке недостаточно чтобы решить данную задачу. Поэтому, я написал вот такой вот код:
Код:
#include <iostream>
#include <algorithm>
using namespace std;

void copy(int * a, int * b, int n) {
    for (int i = 0; i < n; ++i)
        b[i] = a[i];
}

int main() {
    const int a_size = 16;
    int a[a_size], b[a_size], c[a_size];
   
    for (int i = 0; i < a_size; ++i)
        a[i] = i+1;
       
    for (int size = 2; size <= 11; ++size) {
        sort(a, a+size);
        int count_max = 0, perm_num = 1, max_perm_num;
        do {
            int count = 0;
            copy(a, b, size);
            quick_sort(b, 0, size-1, count);
            if (count_max < count) {
               max_perm_num = perm_num;
               count_max = count;
               copy(a, c, size);
            }
            ++perm_num;
        } while (next_permutation(a, a+size));
       
        cout << size << " : " << count_max << endl;
        cout << max_perm_num << endl;
        for (int i = 0; i < size; ++i)
            cout << c[i] << ' ';
        cout << endl << endl;
    }
    {
        int n;
        cin >> n;
    }
   return 0;
}


В данной коде перебираются все перестановки, и выводится та, на которой сортировка сделала больше всего сравнений (значение count было максимальным)
Вывод данной программы:
Код:
        size: 2
       count: 3
perestanovka: 1
1 2

        size: 3
       count: 6
perestanovka: 2
1 3 2

        size: 4
       count: 12
perestanovka: 5
1 4 2 3

        size: 5
       count: 19
perestanovka: 18
1 4 5 3 2

        size: 6
       count: 27
perestanovka: 69
1 4 6 3 2 5

        size: 7
       count: 36
perestanovka: 332
1 4 6 7 2 5 3

        size: 8
       count: 46
perestanovka: 1899
1 4 6 8 2 5 3 7

        size: 9
       count: 57
perestanovka: 12832
1 4 6 8 9 5 3 7 2

        size: 10
       count: 69
perestanovka: 99297
1 4 6 8 10 5 3 7 2 9

        size: 11
       count: 82
perestanovka: 871118
1 4 6 8 10 11 3 7 2 9 5


Я предполагаю, что этих данных достаточно чтобы найти закономерность и научиться генерировать
худшие случаи для массивов больших размеров. Для данной задачи требуется сгенерировать массив
размера 70000.

Помогите мне найти закономерность.

 Профиль  
                  
 
 Re: Худший случай для Быстрой сортировки
Сообщение19.06.2015, 22:40 
Заслуженный участник


04/05/09
4582
Плохо выбрать не только самый большой элемент, но и самый маленький.
Т.е. наихудших для этого варианта quicksort перестановок очень много - $2^{n-1}$. Некоторые из них имеют очень простую структуру.

 Профиль  
                  
 
 Re: Худший случай для Быстрой сортировки
Сообщение20.06.2015, 02:02 


17/04/15
46
frankenstein в сообщении #1029018 писал(а):
Но, я считаю, что одной теоретической информации о сортировке недостаточно чтобы решить данную задачу.

Решение кроется чуть выше.
frankenstein в сообщении #1029018 писал(а):
Ясно что для быстрой сортировки, худший случай, когда она в качестве опорного элемента выбирает максимальный в подмассиве, который сортирует, в такой случае глубина рекурсии будет N.

Осталось понять какой порядок выбора опорного элемента

 Профиль  
                  
 
 Re: Худший случай для Быстрой сортировки
Сообщение20.06.2015, 10:03 


10/05/13
251
venco в сообщении #1029028 писал(а):
Плохо выбрать не только самый большой элемент, но и самый маленький.
Т.е. наихудших для этого варианта quicksort перестановок очень много - $2^{n-1}$. Некоторые из них имеют очень простую структуру.

Да, наименьший тоже.
Я не могу определить эту вот структуру.

 Профиль  
                  
 
 Re: Худший случай для Быстрой сортировки
Сообщение20.06.2015, 10:42 


24/05/09

2054
frankenstein в сообщении #1029018 писал(а):
Я предполагаю, что этих данных достаточно чтобы найти закономерность и научиться генерировать
худшие случаи для массивов больших размеров. Для данной задачи требуется сгенерировать массив
размера 70000.
Помогите мне найти закономерность.


Чё то больно мудрёно - то что вы предлагаете. Не проще ли сгенерировать реальный массив из 70000 цифр в случайном порядке, и сортировать его, выбирая в качестве опорного элемента разные числа: минимальное, близкое к минимальному, 1/4, 1/3, среднее, близкое к среднему, 2/3, 3/4, близкое к максимальному, максимальное. И смотреть как меняется требуемое для каждого случая число перестановок.

 Профиль  
                  
 
 Re: Худший случай для Быстрой сортировки
Сообщение20.06.2015, 10:55 


10/05/13
251
Alexu007
дело в том что код сортировки, по условию задачи, нельзя менять.
А если сгенерировать случайный массив, нет 100% гарантии, что
на нем сортировка сработает худшим образом.

 Профиль  
                  
 
 Re: Худший случай для Быстрой сортировки
Сообщение20.06.2015, 16:57 
Заслуженный участник


04/05/09
4582
frankenstein в сообщении #1029074 писал(а):
Да, наименьший тоже.
Я не могу определить эту вот структуру.
Ну я вот попробовал наобум чередовать минимальный и максимальный элементы, и получилость нечто очень регулярное. Но вам придётся разобраться в алгоритме, что же именно он делает с массивом в таких случаях.

 Профиль  
                  
 
 Re: Худший случай для Быстрой сортировки
Сообщение20.06.2015, 17:05 
Заслуженный участник


26/05/14
981
Вы можете ухудшить массив который сортируете. Для этого надо в каждый элемент надо добавить его индекс в исходном массиве. Назовём такой индекс исходным. Всякий раз когда сортировка выбирает ключ, печатайте исходный индекс. Берёте первый напечатанный исходный индекс и на это место записываете максимальный элемент в массиве. Снова запускаете сортировку. На место второго напечатанного исходного индекса записываете второй по величине элемент в массиве. И так далее. Надо только помнить, для определения следующего исходного индекса надо заново прогнать сортировку, так как изменение значения в текущем исходном индексе меняет все последующие распечатанные исходные индексы. Эту процедуру можно превратить в алгоритм, который за $N^3$ найдёт наихудший массив длины $N$. Небольшая оптимизация поможет сократить время до $N^2$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group