На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Быстрая сортировка , Поиск "плохого" теста
    Известно, что у "быстрой" сортировки (QuickSort) среднее число сравнений пропорционально O(N*logN). Хотя с дополнением, что для некоторых случаев оно стремится к O(N^2). Но нигде не сказано, как получить такой пример! mad.gif
    Мой вопрос сводится к тому, как работают генераторы "плохих" тестов для сортировок. Можно ли написать программу, которая для некоторго метода сортировки с сложностью O(N*logN) выдает пример входных данных, при которых сложность становится O(N^2)?
      помоему ето ересь!! у быстрой сортировки не может быть больше чем O(N*logN)! наверное ето ещё у какоголибо метода
        2 wormball
        В быстрой сортировке массив разделяется на 2 части: элементы, меньшие заданного ключа - в одну, а большие - в другую. Потом эти части сортируются отдельно и склеиваются вместе. Фишка в том, что может получиться так, что на каждом шаге массив из N элементов будет делиться на 2 подмассива: из 1 элемента и из (N - 1) элемента. Так понадобится O(N) сортировок, что дает суммарное время O(N^2).
        O(N*logN) - это когда массив всегда делится на 2 примерно равные по размеру части.

        2 Lucifer:
        Это серьезно, или тонкий юмор?!

        Вот, например, какой самый "плохой" тест для quicksort-а из Паскаля?

        procedure quicksort(var a: list; Lo,Hi: integer);

        procedure sort(l,r: integer);
        var
         i,j,x,y: integer;
        begin
         i:=l; j:=r; x:=a[(l+r) DIV 2];
         repeat
           while a[i]<x do i:=i+1;
           while x<a[j] do j:=j-1;
           if i<=j then
           begin
             y:=a[i]; a[i]:=a[j]; a[j]:=y;
             i:=i+1; j:=j-1;
           end;
         until i>j;
         if l<j then sort(l,j);
         if i<r then sort(i,r);
        end;
          А причем здесь мама и папа?

          PS: тема уходит в offtopic...
            ну тогда я думаю ето просто числа, расположенные в обратном порядке.
              Тогда quicksort из раскидает за один проход! biggrin.gif biggrin.gif biggrin.gif
              Т.е. более N сравнений, IMHO, не будет.
                Да не обязательно в обратном... Просто в некоторых реализациях быстрой сортировки медиана (тот елемент, справа от которого и слева от которого...) выбирается случайным образом. Поетому генератором "плохих" входных последовательностей, на самом деле является математический объект, который фсе привыкли называть "демон". Ен точно знает, какая последовательность будет самой плохой. И неважно откуда, лишь бы выполнялось условие существования етой самой плохой последовательности. smile.gif

                Если медиана выбирается каким-то определенным образом, надо разместить елементы массива так, чтобы ета самая медиана не делила массив на части. (т.е., всегда оказывалась минимальным или максимальным елементом сортируемой подпоследовательности).
                Сообщение отредактировано: Visitor -
                  Цитата
                  Visitor, 11.12.03, 15:22
                  математический объект, который фсе привыкли называть "демон"

                  ты ещё скажи шайтан smile.gif
                  тогда наоборот: чтобы они уже были в правильном порядке рассортированы. тоесь она поймёт, что все последующие числа больше первого, и честно вызовет саму себя с массивом, меньшим на один элемент. кстати если они в обратном порядке, так тоже произойдёт. smile.gif
                    Не, тогда сложность логарифмической останется....
                      Ура! Нашел генерилку! Кому интересно, сюда!
                        Цитата
                        Visitor, 11.12.03, 16:07
                        Не, тогда сложность логарифмической останется....

                        почему??
                          Дык массив так и будет делиться пополам на каждой итерации...
                            в томто и дело, что так он будет делиться не пополам, а будет делиться на часть нулевого размера и часть, где будет почти весь массив. а потому она претерпит n самовызовов, и сложность будет n^2. cool.gif
                              Да, можно в процедуру сортировки вставлять проверку "а не отсортирован ли уже массив?", и тогда некоторые часные случаи будут обрабатываться сами собой. Обычно для алгоритмов сортировки условие конца работы несколько проще.
                                ну ето будет имхо глупость, так ещё более замедлится. можно делить не первым, а средним элементом. а есь ещё помнится двухсторонняя быстрая сортировка.
                                  Брр... А как медиана-то выбирается тогда, если не пополам?
                                    Цитата
                                    Да не обязательно в обратном... Просто в некоторых реализациях быстрой сортировки медиана (тот елемент, справа от которого и слева от которого...) выбирается случайным образом.

                                    От выбора медианы зависит только пример плохого теста. Какую бы мы медиану не выбрали бы, всегда можно будет получить сложность N^2.
                                    Часто медиану считают так: med:=(a[l] + a[r] + a[(l+r) div 2]) div 3;
                                      :lol: Помогите!!!! Кто знает алгоритм БЫСТРОЙ СОРТИРОВКИ???????
                                        Код - Быстрая сортировка (сообщение #261491)
                                        Алгоритм - берем массив, выбираем медиану X. Расбрасываем числа так, чтобы слева от медианы были числа меньше X, а справа - больше X. Сортируем отдельно левую и правые части (рекурсивно тем же самым алгоритмом)
                                          Алгоритм - берем массив, выбираем случайный элемент массива X. Расбрасываем числа так, чтобы слева от медианы были числа меньше X, а справа - больше X. Сортируем отдельно левую и правые части (рекурсивно тем же самым алгоритмом)
                                            Самый плохой тест (получено эмпирически) - если множество элементов массива состоит их 2 элементов - 0 и 1 или только их одного элемента. По поводу порядка их размещения я не знаю. Еще раз повторю, что это получено эмпирически.
                                              Тут уже ссылку кинули на генератор квадратичных тестов для qsort, чтобы qsort работала достаточно быстро проще всего выбирать медиану для разбиения произвыольным образом, то есть рандомный элемент, тогда шанс, что qsort будет работать за квадратичное время будет ничтожно мал. Если надо еще увеличить скорость, то можно не сортировать массивы длиной менее C (С - некоторая константа). В итоге получим "почти сортированный" массив, который можнно отсортировать примитивным алгоритмом, который быстро сортирует "почти отсортированные" массивы. Выигрыш насколько я помню около 15%.
                                                А есть версия алгоритма быстрой сортировки где в качестве индексов массива используются без знаковые (byte, word, cardinal) переменные?
                                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                                0 пользователей:


                                                Рейтинг@Mail.ru
                                                [ Script execution time: 0,0441 ]   [ 16 queries used ]   [ Generated: 19.03.24, 03:42 GMT ]