навеяло мессагой http://www.rsdn.ru/forum/Message.aspx?mid=139064&only=1

Автор: TheGrey
Дата: 25.11.02

Сортировка за O(N) операций. Сортирует, правда, только массивы целых (это принципиально). Можно и для signed, но это немного посложнее будет. Можно и строки сортировать, но тогда это уже будет bucket sort

void KBAK(unsigned long* a, size_t size, unsigned long flag)
{
    if(size==0)
        return;
    size_t i=0, j=size-1;
    while(i<j)
        if((a[j]&flag)!=0)
            j--;
        else if((a[i]&flag)==0)
            i++;
        else
        {
            unsigned long t=a[i];
            a[i]=a[j];
            a[j]=t;
            i++;
        }
    j++;
    flag/=2;
    if(flag)
    {
        KBAK(a, j, flag);
        KBAK(a+j, size-j, flag);
    }
}

void KBAK_COPT(unsigned long* a, size_t size)
{
    KBAK(a, size, 1ul<<(sizeof(unsigned long)*8-1));
}

и тест:

#include <iostream>
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
    unsigned long a[10]={100, 432, 2, 1, 9, 334, 22, 1, 10, 87};
    size_t i;
    for(i=0;i<10;i++)
        cout << a[i] << ' ';
    cout << endl;
    KBAK_COPT(a, 10);
    for(i=0;i<10;i++)
        cout << a[i] << ' ';
    cout << endl;
    cin.get();
    return 0;
}

— вроде бы пашет

Можно, конечно, оптимизировать — и будет еще быстрее работать

Так что теперь, если вашу задачу проще решать на сортированном массиве, но от вас требуют линейного времени, можете смело сортировать!

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

A>Сортировка за O(N) операций. Сортирует, правда, только массивы целых (это принципиально). Можно и для signed, но это немного посложнее будет. Можно и строки сортировать, но тогда это уже будет bucket sort

A>Так что теперь, если вашу задачу проще решать на сортированном массиве, но от вас требуют линейного времени, можете смело сортировать!

Блестяще!

Для строк (и вообще для данных размером M бит) время O(N*M), что в случае со строками, естественно, неприемлимо.

Сортировка чисел со знаком (в дополнительном коде): прикол состоит в том, чтобы по старшему биту упорядочивать наоборот: единица меньше нуля.

Сортировка вещественных чисел также возможна:

union IEEE_FLOAT_32
{
  struct
  {
    signed int sign:1;      // сначала сортируем по знаку
    signed int exponent:8;  // затем - по порядку
    signed int mantissa:23; // и, наконец, по мантиссе
  }
  float value;
};

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

К>Блестяще!

спасибо

К>Для строк (и вообще для данных размером M бит) время O(N*M), что в случае со строками, естественно, неприемлимо.

Ну для строк есть похожий метод. Там они сразу по байтам раскидываются, bucket sort называется.

К>Сортировка чисел со знаком (в дополнительном коде): прикол состоит в том, чтобы по старшему биту упорядочивать наоборот: единица меньше нуля.

угу, это я сразу сообразил, просто не захотел код усложнять.

К>Сортировка вещественных чисел также возможна:

круто. Не знал Т.е. задача сводится к сортировке signed long'ов.
К>

К>union IEEE_FLOAT_32
К>{
К>  struct
К>  {
К>    signed int sign:1;      // сначала сортируем по знаку
К>    signed int exponent:8;  // затем - по порядку
К>    signed int mantissa:23; // и, наконец, по мантиссе
К>  }
К>  float value;
К>};
К>

Вот только беда с этим методом в том, что O(N) — это асимптотика и реальный выигрыш для long'ов будет только при размерах массивов от 4 гигаштук и выше.

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

К>>Для строк (и вообще для данных размером M бит) время O(N*M), что в случае со строками, естественно, неприемлимо.

A>Ну для строк есть похожий метод. Там они сразу по байтам раскидываются, bucket sort называется.
Я имел в виду — неприемлимо долго: M=(8*max(strlen))

К>>Сортировка вещественных чисел также возможна:

A>круто. Не знал Т.е. задача сводится к сортировке signed long'ов.
К>>

К>>union IEEE_FLOAT_32
К>>{
К>>  struct
К>>  {
К>>    signed int sign:1;      // сначала сортируем по знаку
К>>    signed int exponent:8;  // затем - по порядку
К>>    signed int mantissa:23; // и, наконец, по мантиссе
К>>  }
К>>  float value;
К>>};
К>>

Только нужно будет учитывать особенности каждого бита.

A>Вот только беда с этим методом в том, что O(N) — это асимптотика и реальный выигрыш для long'ов будет только при размерах массивов от 4 гигаштук и выше.

Почему это?

Предположим, что фрагментация массива размером N составляет
— метрика D0 — количество элементов не на своих местах; 0 <= D0 <= N
— метрика D1 — сумма расстояний элементов до своих мест; D0 <= D1 <= N*(N+1)/2 (вроде бы)

Аксиома:
— количество сравнений у любой сортировки — не менее N-1.
— количество перестановок — не менее D0/2.

(Есть еще теорема, что достаточное количество сравнений равно log2(N!) — двоичный поиск на пространстве перестановок).

Сортировка пузырьком займет
— N-1 + D1/2 сравнений,
— D1/2 перестановок.

Сортировка кваксорт
— N * M сравнений
— от D0/2 до D0/2 * M перестановок (как повезет)

Поэтому кваксорт уделает пузырьковую при N > 8 (в среднем! Естественно, что для упорядоченного массива пузырек сделает ровно N-1 проверок, что является абсолютным рекордом).
среднее(D0) = N/2
среднее(D1) = (N^2)/4

(N^2)/4/2 > N/2/2*32
N^2 > 64
N > 8

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

A>- вроде бы пашет

У меня получилось вот что:
100 432 2 1 9 334 22 1 10 87
1 1 2 10 9 22 87 100 334 432

Или это только у меня???

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

VVV>У меня получилось вот что:
VVV>100 432 2 1 9 334 22 1 10 87
VVV>1 1 2 10 9 22 87 100 334 432

VVV>Или это только у меня???

Ух ты! И у меня появилось! раньше не было

тогда так:

void KBAK(unsigned long* a, size_t size, unsigned long flag)
{
    if(size==0)
        return;
    size_t i=0, j=size-1;
    while(i<j)
        if((a[j]&flag)!=0)
            j--;
        else if((a[i]&flag)==0)
            i++;
        else
        {
            unsigned long t=a[i];
            a[i]=a[j];
            a[j]=t;
            i++;
            j--;
        }
    j++;
    flag/=2;
    if(flag)
    {
        KBAK(a, j, flag);
        KBAK(a+j, size-j, flag);
    }
}

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

уже лучше

    unsigned long a[10]={1, 2, 3, 4, 5, 5, 4, 3, 2, 1};

1 2 3 4 5 5 4 3 2 1
4 1 1 2 2 3 3 4 5 5

ну так должно быть совсем хорошо

void KBAK(unsigned long* a, size_t size, unsigned long flag)
{
    if(size==0)
        return;
    size_t i=0, j=size-1;
    while(i<j)
    {
        while(i<j && (a[j]&flag)!=0)
            j--;
        while(i<j && (a[i]&flag)==0)
            i++;
        if(i>=j)
            break;
        unsigned long t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
    flag/=2;
    i++;
    if(flag)
    {
        KBAK(a, i, flag);
        KBAK(a+i, size-i, flag);
    }
}

void KBAK_COPT(unsigned long* a, size_t size)
{
    KBAK(a, size, 1ul<<(sizeof(unsigned long)*8-1));
}

#include <iostream>
#include <ctime>
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
    unsigned long a[10];
    srand(time(NULL));
    size_t i;
    for(i=0;i<10;i++)
    {
        a[i]=rand();
        cout << a[i] << ' ';
    }
    cout << endl;
    KBAK_COPT(a, 10);
    for(i=0;i<10;i++)
        cout << a[i] << ' ';
    cout << endl;
    cin.get();
    return 0;
}

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

A>ну так должно быть совсем хорошо

18565 15713 4289 28722 14046 7889 12869 22640 15627 24532
7889 4289 15713 12869 14046 15627 18565 22640 24532 28722

23292 15655 3120 11499 5609 23375 9258 28641 1430 22231
1430 3120 5609 9258 11499 15655 23375 22231 23292 28641

29986 18566 22076 7526 7988 23385 19438 3604 17190 19412
3604 7988 7526 17190 18566 19412 19438 22076 23385 29986

...
...

void init(unsigned long *a, int size)
{
    for(size_t i=0; i < size; i++)
        a[i]=rand();
}

bool test(unsigned long *a, int size)
{
    for(size_t i=0; i < size-1; i++)
    {
        if(a[i] > a[i+1])
            return false;
    }

    return true;
}


...
    for(int i=0; i < 1000; i++)
    {
        init(a, 10);
        unsigned long acpy[10];
        memcpy(acpy, a, sizeof(a));

        KBAK_COPT(a, 10);
        if(!test(a, 10))
        {
            int i;
            for(i=0; i < 10; i++)
                cout << acpy[i] << " ";
            cout << endl;
            for(i=0; i < 10; i++)
                cout << a[i] << " ";
            cout << endl << endl;
        }
    }
...

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

<>

Вот валидированный (доказанный) код; доказательство — см. комментарии.
Обозначение:
)j) -- элемент перед j (т.е. с индексом j-1) -- по аналогии с полуинтервалом [i,j)

inline void swap(unsigned& a, unsigned& b)
{
  unsigned c = a; a = b; b = c;
}

// sort a range [i, j)
void ksort_bit(unsigned* array, unsigned i0, unsigned j0, unsigned bit)
{
    // precondition:
    //   a[0,i0), a[i0,j0), a[j0,size) higher bits are constant
    //   a[0,i0) < a[i0,j0) < a[j0,size)
    // invariant: no changes out of [i0,j0)
    // postcondition:
    //   a[i0,j0) is sorted

    if(j0-i0 < 2)     return; // either empty or single item

    unsigned i = i0, j = j0;

    // precondition: [i,j) is valid range
    // invariant: a[i0,i) bit is clear, a[j,j0) bit is set, [i,j) is valid range (may be empty)
    // postcondition i == j, a[i0,i) bit is clear, a[j,j0) bit is set
    // thus, a[i0,i) < a[j,j0)
    while(i < j)
    {
        // skip i while a[i] bit is clear
        while(i < j && (array[i] & bit) == 0)
            i++;
        // array[i0,i) bit is clear;
        // i==j or array[i] bit is set

        // skip j while a)j) bit is set
        while(i < j && (array[j-1] & bit) != 0)
            j--;
        // array[j+1,j0) bit is set
        // i==j or array)j) bit is clear

        if(i == j) // done
            break;

        // misorder: a[i] > a)j)
        assert(j-i > 1); // because a[i] set, a)j) clear ==> a[i] != a)j) ==> i != j-1
        // exchange boundary items of [i,j)
        swap(array[i], array[j-1]);
        i++;
        j--;
        // invariant is true
    }
    assert(i == j);

    bit >>= 1;
    if(!bit)    return;

    ksort_bit(array, i0, i, bit);
    ksort_bit(array, i, j0, bit);

    // result of recursion:
    //  a[i0,i) is sorted;
    //  a[i,j0) is sorted;
    //  a[i0,i) < a[i,j0) ==> a[i0,j0) is sorted
    // postcondition is true
}

inline void ksort(unsigned* array, unsigned size)
{
    ksort_bit(array, 0, size, 1<<(sizeof(unsigned)*8-1));
}

При желании можно сделать то же самое не на индексах, а на обобщенных итераторах.

template<class iter>
void ksort_bit(iter begin, iter end, unsigned bit);

Как обычно, указываем полуинтервал, то есть итератор конца лежит за правой границей контейнера

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

К>

К>    if(j0-i0 < 2)     return; // either empty or single item
К>

Вот про это-то я и забыл. Все, надо ужинать и спать, а то еще не таких багов наделаю.
Зато теперь можно смело сортировать за линейное время! Общими усилиями алгоритм довели до конца. Вроде бы...
А гн-у Кодту предлагаю присвоить звание Главного Линейного Программиста

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

Интересная штука но для массивов меньше 2^(sizeof(type)*8) я выбераю qsort.

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

WH>Интересная штука но для массивов меньше 2^(sizeof(type)*8) я выбераю qsort.

Почему?
O(qsort) = O(n*log2(n)) -- в среднем, O(n^2) -- в худшем случае
O(ksort) = O(n*s) -- всегда
s = количество разрядов

Q*n*log2(n) <> K*s*n
(Q,K — некоторые константы)
log2(n) <> s*K/Q
n <> 2^(s*K/Q)

W*n^2 <> K*s*n
n <> s*K/W

вопрос в том, чему равно отношение K/Q, K/W

Вот реализация STL из VS7 уходит в qsort'е максимум на 1.5*log2(N) (а меньше, чем log2(N) и не бывает) шагов и те куски, которые за такое число итераций не отсортировались, сортирует heapsort'ом или insertsort'ом в зависимости от размера кусков. В общем, в худшем случае std::sort сделает 1.5*log2(N) проходов (каждый проход там имеет такую же сложность что и в ksort вроде бы). Короче, надо все на практике проверять
Вот я тут тест слабал, получилось, что при сортировке массива ULONG размером в 10 млн. эл-тов std::sort работает на 20% быстрее, а при 50 млн. — на 10%. Большие массивы в память плохо влазят
Для USHORT с 50 млн. элементами ksort выигрывает 25%.
Все сугубо на моем компе.

const size_t N=50000000;

void prepare(T* a)
{
    size_t i;
    for(i=0;i<N;i++)
        a[i]=rand();
    std::sort(a, a+N/4);
    std::sort(a+N/4*3, a+N, std::greater<T>());
}

int _tmain(int argc, _TCHAR* argv[])
{
    T* a=new T[N];
    srand(time(NULL));

    for(size_t j=0;j<10;j++)
    {
        prepare(a);

        clock_t t=clock();
        ksort(a, N);
        cout <<"t1=" << clock()-t << endl;

        prepare(a);

        t=clock();
        std::sort(a, a+N);
        cout <<"t2=" << clock()-t << endl;

        cout<<endl;
    }
        delete[] a;
    cin.get();

    return 0;
}

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

A>навеяло мессагой http://www.rsdn.ru/forum/Message.aspx?mid=139064&amp;only=1

Автор: TheGrey
Дата: 25.11.02

A>Сортировка за O(N) операций. Сортирует, правда, только массивы целых (это принципиально). Можно и для signed, но это немного посложнее будет. Можно и строки сортировать, но тогда это уже будет bucket sort

Ой-ой-ой! А есть ли строгое матеметическое доказательство???
Я тут тестик написал — нифига нелинейное время.
Да и по алгоритму это можно заметить.
Растет нелинейно — правда не так сильно.
Может это логарифм, только более слабый, чем quick sort.

void main() 
{
    const int count = 1000000;
    unsigned *ar = new unsigned[count];
    for (int i = 0; i < count; ++i)
    {
        ar[i] = (rand() | (rand() << 16)); // set more random bits :)
    }
    cout << endl;

    time_t t1 = clock();

// does this give a linear time?
    ksort(ar, count);

/* this should give truly linear time
    for (i = 0; i < count*10; ++i)
    {
        ar[i%count] = ar[count-(i%count)-1]; // nothing special
    }
*/
    time_t t2 = clock();

    cout << "time="<<(t2-t1)<<endl;
    delete ar;
}

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

S>Ой-ой-ой! А есть ли строгое матеметическое доказательство???
S>Я тут тестик написал — нифига нелинейное время.
S>Да и по алгоритму это можно заметить.
S>Растет нелинейно — правда не так сильно.
S>Может это логарифм, только более слабый, чем quick sort.

Учите матчасть, товарищь!
O(N) — это значит линейное в асимптотике. И проверять это надо, действительно, аналитически (или методом внимательного всматривания), а не тестами.

И еще, не забывайте про особенности работы памяти, кэша и мн. мн. др. Так что clock() не показатель.

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

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

S>>Ой-ой-ой! А есть ли строгое матеметическое доказательство???
S>>Я тут тестик написал — нифига нелинейное время.
S>>Да и по алгоритму это можно заметить.
S>>Растет нелинейно — правда не так сильно.
S>>Может это логарифм, только более слабый, чем quick sort.

A>Учите матчасть, товарищь!
A>O(N) — это значит линейное в асимптотике. И проверять это надо, действительно, аналитически (или методом внимательного всматривания), а не тестами.

A>И еще, не забывайте про особенности работы памяти, кэша и мн. мн. др. Так что clock() не показатель.

я проверял от 1млн до 20млн — разница растет, а для асимптотического приближения она должна уменьшаться.
На счет матчасти — а можно ссылочку пожалуйста?
Буду очень рад ознакомиться.

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

S>я проверял от 1млн до 20млн — разница растет, а для асимптотического приближения она должна уменьшаться.

вот как раз где-то тут а начинает сказываться размер кэша 2-го уровня.

S>На счет матчасти — а можно ссылочку пожалуйста?
S>Буду очень рад ознакомиться.

уж и не помню... про пределы и асимптотику написано во всех учебниках по мат. анализу

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

S>Ой-ой-ой! А есть ли строгое матеметическое доказательство???
Ключевые слова: константная глубина рекурсии.

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

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

VVV>>У меня получилось вот что:
VVV>>100 432 2 1 9 334 22 1 10 87
VVV>>1 1 2 10 9 22 87 100 334 432

VVV>>Или это только у меня???

A>Ух ты! И у меня появилось! раньше не было

Даа, товарищь Atilla. Подобные вещи надо проверять прежде чем постить. Ну хотя бы простейшим стресс-тестированием, как у VVV. Ну это так, замечание на будущее.

На самом деле, если на практике способ работает медленнее, то что с него толку? Вот например, сложность quick sort равна O(N^2). Сложность merge sort гарантирует O(N*log(N)). Тем не менее, грамотно имплементированный quick sort кроет merge sort как бык овцу, не требуя при этом дополнительной памяти (я не говорю о случаях, когда merge sort — единственно возможный вариант). Да, quick sort затыкается на почти отсортированных массивах. Но даже в этом случае, если вероятность подать на вход отсортированный массив весьма значительна (ну, скажем, 1/1000000), то проще бывает всегда делать shuffle + quick sort, чем просто merge sort (феномен, но это так). А вообще-то, все от задачи зависит. Не бывает идеальной сортировки, так же как и не бывает универсального растворителя. На практике, qsort дает почти линейное время, но этот факт вообще-то, не имеет никакого отношения к теоретическому понятию Big-Oh-Notation.