Имеется массив из n объектов. У объектов есть ключ, принимающих два значения: 0 или 1.
Надо придумать максимально эффективный алгоритм, который выполняет стабильную сортировку массива по ключу.
Объём дополнительно используемой памяти должен быть O(1).

Задача наверняка известная и изученная. Фактически, надо реализовать stable_partition из STL с ограничением на объём дополнительной памяти. Лучший алгоритм, который я смог придумать, в худшем случае имеет сложность O(n*log(n)). Можно ли как-то быстрее? Если нельзя, то почему?

Здравствуйте, mrk84, Вы писали:

M>Имеется массив из n объектов. У объектов есть ключ, принимающих два значения: 0 или 1.
M>Надо придумать максимально эффективный алгоритм, который выполняет стабильную сортировку массива по ключу.
M>Объём дополнительно используемой памяти должен быть O(1).

Ну придумай что-нить сам. Что-то типа такого

type
  TSomeObject = class
    Key: Boolean;
    // Other fields
  end;  

procedure SortArray(var A: array of TSomeObject);
var
  Lo, Hi: Integer;
  SavedLo: TSomeObject;
begin
  Lo := Low(A);
  Hi := High(A);
  repeat
    if Lo >= Hi then Exit;

    while A[Lo] = False do
    begin
      Lo := Lo + 1;
      if Lo >= Hi then Exit;
    end;

    while A[Hi] = True do 
    begin
      Hi := Hi - 1;
      if Lo >= Hi then Exit;
    end;

    SavedLo := A[Lo];
    A[Lo] := A[Hi];
    A[Hi] := SavedLo;

    Lo := Lo + 1;
    Hi := Hi - 1;
  until False;
end;

Здравствуйте, Mystic, Вы писали:

M>Ну придумай что-нить сам. Что-то типа такого

в том-то и дело, что этот очевидный алгоритм нестабилен, а другой очевидный — использует O(n) памяти

Здравствуйте, BulatZiganshin, Вы писали:

BZ>Здравствуйте, Mystic, Вы писали:

M>>Ну придумай что-нить сам. Что-то типа такого

BZ>в том-то и дело, что этот очевидный алгоритм нестабилен
А разве его нельзя превратить в стабильный, реверснув после прохода часть последовательности?

BZ>а другой очевидный — использует O(n) памяти
радиксную сортировку? да, первое что пришло в голову. Но по памяти далеко не O(1)

Здравствуйте, samius, Вы писали:

BZ>>в том-то и дело, что этот очевидный алгоритм нестабилен
S>А разве его нельзя превратить в стабильный, реверснув после прохода часть последовательности?

какую? у нас смешиваются аборигены и понаехалы

Здравствуйте, samius, Вы писали:

S>Здравствуйте, BulatZiganshin, Вы писали:

BZ>>в том-то и дело, что этот очевидный алгоритм нестабилен
S>А разве его нельзя превратить в стабильный, реверснув после прохода часть последовательности?

нет, нельзя. Спать пора!

Здравствуйте, mrk84, Вы писали:

M>Имеется массив из n объектов. У объектов есть ключ, принимающих два значения: 0 или 1.
M>Надо придумать максимально эффективный алгоритм, который выполняет стабильную сортировку массива по ключу.
M>Объём дополнительно используемой памяти должен быть O(1).

Результат сортировки как будет использоваться? Один-два прохода и все или много-много раз?
В какой пропорции в данных будут 0 и 1 в среднем?

Здравствуйте, wildwind, Вы писали:

W>Результат сортировки как будет использоваться? Один-два прохода и все или много-много раз?
А это имеет значение?

W>В какой пропорции в данных будут 0 и 1 в среднем?
В любых. Сложность алгоритма оценивается по худшему варианту.

Здравствуйте, Mystic, Вы писали:

M>Ну придумай что-нить сам. Что-то типа такого

Это не стабильная сортировка.
Стабильная сортировка не меняет относительный порядок элементов с одинаковым ключом.

Здравствуйте, mrk84, Вы писали:

W>>Результат сортировки как будет использоваться? Один-два прохода и все или много-много раз?
M>А это имеет значение?

Ну раз общего решения не видно, то подумал, что в случае одноразового использования можно схитрить. Ничего не сортировать, в качестве результата вернуть итератор, который идет по исходному массиву и пропускает сначала 1 потом 0.

Здравствуйте, mrk84, Вы писали:

M>Имеется массив из n объектов. У объектов есть ключ, принимающих два значения: 0 или 1.
M>Надо придумать максимально эффективный алгоритм, который выполняет стабильную сортировку массива по ключу.
M>Объём дополнительно используемой памяти должен быть O(1).

M>Задача наверняка известная и изученная. Фактически, надо реализовать stable_partition из STL с ограничением на объём дополнительной памяти. Лучший алгоритм, который я смог придумать, в худшем случае имеет сложность O(n*log(n)). Можно ли как-то быстрее? Если нельзя, то почему?

Решение
память: O(1)
сравнений: O(n*log(log(n))) // часто по ним считают время...
время: O(n*log(n)) // время тратится, в основном, на swap, а не на сравнение


Если на пальцах:
1) Делим интервал пополам.
2) Сортируем отдельно правую и левую половины.
3) Находим где начинаются единицы на каждой из половинок.
4) Переставляем единички из левой половины, с ноликами из правой.

Число вызовов сравнений можно сократить до O(n) (и даже до n, без всяких O), если после каждой перестановки областей (4) сохранять новое положение границы между нолями и единицами, но тогда потребуется O(log(n)) памяти.

Пришлось здорово поизвращаться, чтобы избавиться от рекурсии в реализации.

// Время:O(n), сравнений:0 , n==end-begin
template <class T>
void swap_regions(T* begin, T* mid, T* end)
{
    assert( begin <= mid && mid <= end );

    while ( begin!=mid && mid!=end )
    {
        assert( begin < mid && mid < end );

        if( mid-begin >= end-mid )
        {
            T* mid2=begin + ( (mid-begin) - (end-mid) );
            for(size_t i=0; i< size_t(end-mid); ++i)
                std::swap( mid2[i], mid[i]);

            end=mid;
            mid=mid2;
            begin=begin;
        }
        else 
        {
            T* mid2=mid + (mid-begin);
            for(size_t i=0; i< size_t(mid-begin); ++i)
                std::swap( mid[i], begin[i]);

            begin=mid;
            mid=mid2;
            end=end;
        }
    };
}

template <class T, class Key>
class find_lower_boud_comparer
{
    Key key;
    bool foo(bool b) { return b; }
    bool foo(T t) { return key(t); }
public:
    find_lower_boud_comparer(Key key)
        : key(key)
    {}

    template<class T1, class T2>
    bool operator() (T1 lhs, T2 rhs)
    {
        return foo(lhs) < foo(rhs);
    }
};

// Время:O(log(n)), сравнений:O(log(n)) , n==end-begin
template <class T, class Key>
T* find_lower_boud(T* begin, T* end, Key key)
{
    return std::lower_bound(begin, end, true, find_lower_boud_comparer<T, Key>(key) );
}

// O(n)*CallOf("visitor") , n==end-begin
// Но поскольку средний размер переданный в visitor меньше...
// O(n*log(n)), если  CallOf("visitor") <= O(n)
// O(n*log(log(n))), если  CallOf("visitor") <= O(log(n))
template <class T, class Visitor>
void binary_tree_round(T* begin, T* end, Visitor visitor)
{
    const size_t size = end-begin;
    for(size_t step=2; step < size*2; step *= 2)
    {
        const size_t rounded = size - (size%step);
        for(size_t i=0; i+step<=rounded; i+=step)
            visitor( begin+i, begin+i+step/2, begin+i+step );

        if( (size%step) > step/2 )
            visitor( begin+rounded, begin+rounded+step/2, end);
    }
}

// Время:O(n), сравнений:O(log(n))
template <class T, class Key>
class stable_partition_visitor
{
    Key key;
public:
    stable_partition_visitor(Key key)
        : key(key)
    {}
        // O(log(n))
        // O(log(n)) + O(n) == O(n)
    void operator() (T* begin, T* mid, T* end)
    {
        T* begin2 = find_lower_boud(begin, mid,      key);
        T* end2   = find_lower_boud(       mid, end, key);
        swap_regions(begin2, mid, end2);    
    }
};

// Время:O(n*log(n)), сравнений:O(n*log(log(n)))
template <class T, class Key>
void stable_partition_2(T* begin, T* end, Key key)
{
    binary_tree_round(begin, end, stable_partition_visitor<T, Key>(key) );
}

Здравствуйте, Chorkov, Вы писали:

C>Решение
А на какой из вопросов дает ответ рещение, если оно имеет сложность O(n*log(n)) (понятно, что число сравнений автора врядли интересует — по числу сравнений можно и за O(n) — пустить по массиву два указателя, текущую позицию и позицию, куда надо перемещать нолик, если он встретился) и не доказывает, что нельзя быстрее?

Здравствуйте, mrk84, Вы писали:

M>Надо придумать максимально эффективный алгоритм, который выполняет стабильную сортировку массива по ключу.

M>Задача наверняка известная и изученная. Фактически, надо реализовать stable_partition из STL с ограничением на объём дополнительной памяти.

Вроде задача так и называется: 0-1 sorting problem

M>Лучший алгоритм, который я смог придумать, в худшем случае имеет сложность O(n*log(n)). Можно ли как-то быстрее?

Думал, думал и... ничего не придумал Вот только это (если не ошибаюсь):
Имея дополнительную память объемом k, можно уменьшить сложность алгоритма до .

Т.к. длину буфера k можно выбрать достаточно большим, то можно получить алгоритм близкий к O(N). Используя буфер в 1 кб, получим "сложность" O(4*N) для массивов, помещающихся в 4 Гб памяти компьютера

M>Если нельзя, то почему?

Насчет зя или нельзя — не знаю. Но если найдется такой алгоритм, то из него очевидным способом можно будет получить стабильную сортировку за O(n*log n) с памятью O(1). Судя по таблицам, представленным в http://en.wikipedia.org/wiki/Sorting_algorithm, такие алгоритмов сейчас не известны. В таблицах все они имеют сложность O(n^2).

Здравствуйте, mrk84, Вы писали:

M>Задача наверняка известная и изученная. Фактически, надо реализовать stable_partition из STL с ограничением на объём дополнительной памяти. Лучший алгоритм, который я смог придумать, в худшем случае имеет сложность O(n*log(n)). Можно ли как-то быстрее? Если нельзя, то почему?
оно?. За корректность не поручусь.

Здравствуйте, andyJB, Вы писали:

JB>Здравствуйте, mrk84, Вы писали:

M>>Задача наверняка известная и изученная. Фактически, надо реализовать stable_partition из STL с ограничением на объём дополнительной памяти. Лучший алгоритм, который я смог придумать, в худшем случае имеет сложность O(n*log(n)). Можно ли как-то быстрее? Если нельзя, то почему?
JB>оно?. За корректность не поручусь.

Вот и я смотрел на эту статью, но алгоритм так и не понял
Если кто осилит указанную статью, расскажите на пальцах...

Этот алгоритм сделан на основе другого, описанного в "Stable in situ sorting and minimum data movement" J. I. Munro, V. Raman, J. S. Salowe, 1990, Pages: 220 — 234.
Может у кого есть этот источник?