Войти
ФлеймФорумПрограммирование

Существует ли такая сортировка? (4 стр)

Страницы: 13 4 5 68 Следующая »
#45
15:04, 27 дек 2014

Ох, википедия, конечно, жжот. Как оказалось, я сначала криво понял суть алгоритма (это Median of Medians который),
ибо в моем понимании начали вылезать косяки.
И полностью алгоритм удалось понять только объединив русскую и английскую вики.
Написать так непонятно, что в обоих вики отсутствуют важные куски - это еще надо уметь...

Может свою статью запилить по разъяснению этого алгоритма XD

#46
17:47, 27 дек 2014

Короче, я пока могу реализовать только рекурсивный вариант MofM на списках.
Т.е. решение есть если можно использовать O(logn) памяти.

#47
18:22, 27 дек 2014

TarasB
>я посчитал
>для массива из 5^n элементов гарантируется что 3^n меньше
>это соотношение можно сделать сколь угодно поганым и будет скорее квадрат логарифма
Можешь пример последовательности, для которой найдёт хуже некоторого константного процента (например 5%)?

>local_e не инициализируется до while
Ну так вроде это не проблема.

R.I.P.
>Короче, я пока могу реализовать только рекурсивный вариант MofM на списках.
В той версии вот это:
while((n=std::distance(b,e))>4)
//...
e=dst;
- рекурсия.
(Хвостовая, развёрнутая).

#48
18:30, 27 дек 2014

FordPerfect
> Можешь пример последовательности, для которой найдёт хуже некоторого
> константного процента (например 5%)?

Пусть есть 5^n элементов. Алгоритм выбрал элемент ИКС.
Значит, среди 5 элементов из последней итерации было три элемента, которые не больше, чем икс.
Значит, в препоследей итерации (в которой из 25 элементов выбрали 5 самых средних)  было 9 элементов, которые не больше, чем икс. Про остальные гарантии нет.
На каждой итерации, двигаясь с конца, число элементов в массиве увеличиваем в 5 раз, число элементов, про которые есть гарантия - лишь в три раза.

Пример для 9/25 привести могу. Для остальных лень)

FordPerfect
> Ну так вроде это не проблема.
А, точно.

FordPerfect
> - рекурсия.

Ты рекурсируешь толкьо функцию из первых 2 пунктов. А в википедии имеется в виду рекурсирование полной функции из 5 пунктов.

#49
18:54, 27 дек 2014

TarasB
Ок, похоже на то.

Тупой я сегодня.

#50
18:56, 27 дек 2014

FordPerfect
> В той версии вот это:
> while((n=std::distance(b,e))>4)
> //...
> e=dst;
> - рекурсия.
> (Хвостовая, развёрнутая).
Вы не поняли сути MofM (в прочем, не удивительно, я сам все до конца понял, только когда сопоставил русскую и английскую вики и глянул в статью).
Вы просто много раз берете пятерки чисел, ищете в них медианы, потом 4/5 чисел отбрасываете и повторяете снова.
MofM устроен не так. Там есть аж дерево рекурсии (т.е. из каждого состояния 2 рекурсивных вызова).
Одно из них размера 1/5n, а другое - не более 7/10n (ну, это где-то в анализе всплывает).
В вашей реализации этого нет.

> Можешь пример последовательности, для которой найдёт хуже некоторого константного процента (например 5%)?
Вот генератор

  int Power = 6;
  int p3 = 1, p5 = 1;
  for (int a=0; a<Power; a++)
  {
    p3*=3;
    p5*=5;
  }

  int ii = 0;
  for (int a=0; a<p3; a++)
  {
    int pos = 0, z = a;
    for (int b=0; b<Power; b++)
    {
      pos = pos*5 + z%3;
      z/=3;
    }
    A[pos] = ii++;
  }

  for (int a=1; a<p5; a++)
    if (A[a]==0)
      A[a] = ii++;

  //for (int a=0; a<p5; a++)
  //  cout << A[a] << " ";
  //cout << "\n";

  int pivot = * select_pivot( A, A+p5 );
  cout << "pivot=" << pivot << "\n";
  cout << "total=" << p5 << "\n";
  cout << "percent=" << 100.*pivot/p5 << "\n";

Для Power=6 пишет:

pivot=728
total=15625
percent=4.6592
#51
18:58, 27 дек 2014

R.I.P.
В Кормене (10.3) описание вроде получше, чем в Википедии.

Правка:

Спасибо за пример.

#52
19:10, 27 дек 2014

FordPerfect
> В Кормене (10.3) описание вроде получше, чем в Википедии.
о, он и в кормене есть, видимо у меня старое издание
действительно, в кормене все четко и по существу
и описание там совпадает с моим пониманием

#53
19:27, 27 дек 2014

И он есть на русском.

#54
19:32, 27 дек 2014

FordPerfect
ну, я на русском и прочитал :3

#55
2:02, 28 дек 2014

R.I.P.
Рекурсивная версия примерно так выглядит?

template<typename ForwardIterator>
ForwardIterator median5(ForwardIterator b,ForwardIterator e)
{
    ForwardIterator src_b=b,src_e,dst=b;
    while(src_b!=e)
    {
        size_t m;
        src_e=src_b;
        for(size_t i=0;i<5&&src_e!=e;++i)
            src_e=next(src_e);
        m=std::distance(src_b,src_e);
        bubble_sort(src_b,src_e);
        swap(*dst,*(next(src_b,m/2)));
        src_b=src_e;
        dst=next(dst);
    }
    return dst;
}

template<typename ForwardIterator>
ForwardIterator select(ForwardIterator b,ForwardIterator e,size_t index)
{
    size_t n=distance(b,e);
    size_t p1,p2;
    ForwardIterator med;
    ForwardIterator pivot;
    pair<ForwardIterator,ForwardIterator> range;
    if(n<5)
    {
        bubble_sort(b,e);
        swap(*b,*next(b,index));
        return b;
    }
    med=median5(b,e);
    pivot=select(b,med,distance(b,med)/2);
    range=partition_range(b,e,pivot);
    p1=distance(b,range.first);
    p2=distance(b,range.second);
    if(index<p1) return select(b,range.first,index);
    else if(index<p2) return range.first;
    else return select(range.second,e,index-p2);
}

template<typename ForwardIterator>
ForwardIterator select_pivot(ForwardIterator b,ForwardIterator e)
{
    return select(b,e,distance(b,e)/2);
}
#56
2:24, 28 дек 2014

FordPerfect
да, похоже на правду
даже обошел возможные проблемы если вдруг ключей равных пивоту очень много)

#57
2:49, 28 дек 2014

А ведь я кажется вижу, как реализовать алгоритм без рекурсии.

Смотрите.

Берём K ~ (log(n))^2.

Отводим первые 2*K элементов под "стек" из K бит (порядок чисел значений в каждой паре кодирует 1 бит). Ищем медиану из остатка.
Нужно чтобы числа в каждой паре были различными. Пытаемся выбрать такие элементы (вроде должно быть возможно за O(n)). Если их выбрать не получается, значит у нас много одинаковых элементов и медиана - всё-равно один из них.

Иначе делаем ровно то, что раньше, только вызов/return это явные push/pop + goto. Push/pop имеют сложность O((log(n))^2).
Глубину стека храним явно (O(1)).

log(n)^2 потому, что нужен стек на log(n) слотов, и log(n) на кодирование значения (т. к. и index и distance(b,e) не имеет смысла быть больше n).

Для маленьких размеров - bubble sort.
То, что мы ищем не честную медиану нам не мешает, т. к. (log(n))^2 по сравнению с n не ухудшит сходимость quicksort'а.
Торможу?

Правка: значения - не обязательно числа.

#58
3:12, 28 дек 2014

FordPerfect
о, походу пошли извращения в стиле вот этого: http://habrahabr.ru/post/205290/ )
у меня тоже были мысли насчет кодирования стека чем-нибудь, но у меня там мысли пошли в сторону
"а сколько бит может быть в числе и могу ли я брать многобитные числа и считать, что операции над ними идут за O(1)"
после этих мыслей я забил на дальнейшие рассуждения)

вообще говоря можно всю необходимую инфу по стеку хранить в одном 64-битном числе и этого хватит на все разумные сценарии
но как смотреть с академической точки зрения - я вот хз)

брать для кодирования этого числа сами элементы массива - идея, в принципе, интересная
и вроде бы обходит эту проблему. надо глубже над этим подумать
я щас сам торможу - 5й час ночи местного времени:) с утра (скорее, с дня) на свежую голову подумаю

#59
20:28, 29 дек 2014

FordPerfect
Пришли пару мыслей по поводу организации "стека".
А именно - как искать К различных пар элементов и что делать, если таких нет.
(Ну, чтобы еще было за линию и на списке работало)

Пусть нам надо найти K пар таких чисел.
Просто идем и считаем число пар соседних элементов, которые не равны.
Если их хотя бы 2K-1 - вторым проходом перемещаем К пар в начало списка и спокойно ищем медиану в остатке, юзая эти 2K элементов на нужды стека.
Если их < 2K-1 - то, по принципу Дирихле, найдется кусок подряд идущих равных элементов, длина которого не менее O(N/K). Пусть эти элементы равны x.
Поскольку K - это какая-то там степень логарифма, то N/2K > K, для всех N > некоторой константы.
Теперь проходимся по массиву еще раз и считаем сколько элементов, которые не равны x.
Если их хотя бы K, то образуем пары из них и элементов, которые равны x.
Иначе - у нас тупо почти все элементы одинаковые. Ну, аж N-K+1 штук, как минимум.
И вроде бы N-K+1>C*N, где C константа (ну, опять же для бостаточно большого N), поэтому селект для квиксорта назначаем этот самый элемент x.

Страницы: 13 4 5 68 Следующая »
ФлеймФорумПрограммирование

Тема в архиве.