навеяло мессагой 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.

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

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

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

не совсем. Если с установленным битом окажется только одно число, то рекурсия дальше не пойдет. Единственное что можно сказать, так это то, что число рекурсий точно больше 1 и не больше числа бит. По определению получается O(N).

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

Каюсь! Больше так не буду! программил с большого недосыпа

MS>На самом деле, если на практике способ работает медленнее, то что с него толку?

как же медленнее?? По моим прикидкам, для массивов с N=250 млн. они уже должны сравняться. А для short'ов мой алгоритм выигрывает уже при размерах в несколько миллионов.

MS>Вот например, сложность quick sort равна O(N^2).

У qsort и heapsort средняя сложность O(N*log(N)) И это можно доказать.
Вот только максимальная сложность у первого O(N^2), а у второго O(N*log(N)).

MS>А вообще-то, все от задачи зависит. Не бывает идеальной сортировки, так же как и не бывает универсального растворителя.

Абсолютно с Вами согласен! Но я сразу предупредил, что область применимости этого алгоритма — очень большие массивы.
А задумывалось это вообще, почти как шутка и контрпример на утверждение, что в лучшем случае отсортировать можно за O(N*log(N)), а за O(N) невозможно.

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

A>А задумывалось это вообще, почти как шутка и контрпример на утверждение, что в лучшем случае отсортировать можно за O(N*log(N)), а за O(N) невозможно.

Да я говорил уже — bit_set. Ровно O(N), ураган, сказка, пуля! Только не ясно, что делать потом с этими битами. Обычно предполагается наличие некоего ключа сортировки, с ассоциированным с ним значением. Здесь же связь "ключ-значение" полностью теряется. Тем не менее, область применения метода есть, и весьма обширная.

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

MS>Да я говорил уже — bit_set. Ровно O(N), ураган, сказка, пуля! Только не ясно, что делать потом с этими битами. Обычно предполагается наличие некоего ключа сортировки, с ассоциированным с ним значением. Здесь же связь "ключ-значение" полностью теряется. Тем не менее, область применения метода есть, и весьма обширная.

А что за bit-set? Похоже, я чего-то недопонимаю...

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

A>А что за bit-set? Похоже, я чего-то недопонимаю...

Просто битовый вектор, длинный. Размером max_val-min_val+1 в сортируемом массиве. Выставляем в 1 биты, номера которых соответствуют сортируемым числам. Все. Массив отсортирован, но информация потеряна — во-первых, дублирующиеся значения будут слиты в одно, во-вторых, невозможно восстановить связку "ключ-значение". Впрочем, для такой задачи это неважно: http://www.rsdn.ru/forum/Message.aspx?mid=138606&amp;only=1

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

о чем я и писал: http://www.rsdn.ru/forum/Message.aspx?mid=139437&amp;only=1

Автор: McSeem2
Дата: 26.11.02

Так я же предложил алгоритм, который память не жрет!!!

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

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

Вот тут есть интересная статейка по поводу Radix Sort. http://www.codercorner.com/RadixSortRevisited.htm

S/IU>Вот тут есть интересная статейка по поводу Radix Sort. http://www.codercorner.com/RadixSortRevisited.htm

Действительно инетересно. Вместо O(N*32) получаем O(N*5) при небольшом фиксированном объеме дополнительной памяти. Кто поиграться горазд?

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

MS>Действительно инетересно. Вместо O(N*32) получаем O(N*5) при небольшом фиксированном объеме дополнительной памяти. Кто поиграться горазд?

небольшой объем — это второй массив размером с первый.
Если памяти выделить 1>>sizeof(T), то вобще в 2 прохода выполнится, но ведь идея была сделать без выделения новых массивов: как в пузырьке, qsort'е и т.п.

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

A>А задумывалось это вообще, почти как шутка и контрпример на утверждение, что в лучшем случае отсортировать можно за O(N*log(N)), а за O(N) невозможно.

На самом деле, сложность ksort = O(N*M), где M — разрядность. Очевидно, для множества из N чисел разрядность оных (без повторений) будет не менее log2(N).

Законы комбинаторики не объедешь!
Есть же теорема о сложности сортировки: поскольку число C комбинаций из N элементов равно N! --> (N/e)^N,
то достаточно log2(C) = log2(N!) --> N*log2(N/e) сравнений и N-1 парных перестановок.

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

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

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

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

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

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

Если я не ошибаюсь, господин Atilla, это обычная побитовая сортировка.
Просто смешно как это ученый человек может подумать, что он нагора может за день выдать новый метод сортировки за O(n).

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

cpp>Если я не ошибаюсь, господин Atilla, это обычная побитовая сортировка.

наверное обычная Я на всякий случай тогда пробежался по поисковикам и ничего такого не нашел (были сортировки, когда не бит брался, а несколько разрядов). Вот и сейчас яндекс с рамблером на слова "побитовая сортировка" ничего не выдает...

cpp>Просто смешно как это ученый человек
спасибо

cpp> может подумать, что он нагора может за день выдать новый метод сортировки за O(n).

Вообще-то ветка называется "Исходники", а не "Алгоритмы". Метод новый наверное слабо будет, а вот исходники за часок состряпать — вполне

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

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

cpp>>Если я не ошибаюсь, господин Atilla, это обычная побитовая сортировка.

A>наверное обычная Я на всякий случай тогда пробежался по поисковикам и ничего такого не нашел (были сортировки, когда не бит брался, а несколько разрядов). Вот и сейчас яндекс с рамблером на слова "побитовая сортировка" ничего не выдает...

cpp>>Просто смешно как это ученый человек
A>спасибо

cpp>> может подумать, что он нагора может за день выдать новый метод сортировки за O(n).

A>Вообще-то ветка называется "Исходники", а не "Алгоритмы". Метод новый наверное слабо будет, а вот исходники за часок состряпать — вполне

Я вот тут почитал соседние ветки и задумался.
Господин Atilla, здесь что все серьезно уверены, что асимптотическая скорость Вашего алгоритма O(n)???
Я начинаю впадать в депрессию, так как разница между qsort и bit_sort только в том, что bit_sort не выполняет непосредственных операций сравнения между элементами массива, а использует булеву логику для сравнения с некоторым эталоном. Скорость в данном случае увеличивается только за счет реализации операций булевой логики на x86. Алгоритмическая сложность вашего вновь придуманного велосипеда (см. Яндекс — битовая сортировка) от этого НЕ МОЖЕТ ПАДАТЬ, а именно алгоритмическую сложность и показывает Big-Oh-Notation. (спасибо McSeem2)

С уважением, Сергей.

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

cpp>Я вот тут почитал соседние ветки и задумался.
cpp>Господин Atilla, здесь что все серьезно уверены, что асимптотическая скорость Вашего алгоритма O(n)???

а Вы серьезно уверены, что асимптотическая сложность этого алгоритма O(N*log2(N)) ???

Ну сами подумайте: глубина рекурсии ограничена числом sizeof(value_type)*8 ! На каждой глубине сравнений (или битовых and'ов) может быть N или немного меньше. Итого сравнений примерно 32*N (для unsigned long'ов). У qsort'а же глубина рекурсии может доходить до N! ну а в лучшем случае — log2(N), поэтому и получается такая асимптотика. Другое дело что в большинстве случаев log2(N) < 32 но это уже к асимптотике не имеет отношения

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

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

cpp>>Я вот тут почитал соседние ветки и задумался.
cpp>>Господин Atilla, здесь что все серьезно уверены, что асимптотическая скорость Вашего алгоритма O(n)???

A>а Вы серьезно уверены, что асимптотическая сложность этого алгоритма O(N*log2(N)) ???

A>Ну сами подумайте: глубина рекурсии ограничена числом sizeof(value_type)*8 ! На каждой глубине сравнений (или битовых and'ов) может быть N или немного меньше. Итого сравнений примерно 32*N (для unsigned long'ов). У qsort'а же глубина рекурсии может доходить до N! ну а в лучшем случае — log2(N), поэтому и получается такая асимптотика. Другое дело что в большинстве случаев log2(N) < 32 но это уже к асимптотике не имеет отношения

Стандартный qsort без либ наворотов, т.е. сравнений через функцию:

void Hoar(int C[], int l, int k)
{
    int  i = l, j = k, X = C[(k + l) / 2], T;

    while(i <= j) {
        while(C[i] < X) i++;
        while(X < C[j]) j--;
        if(i <= j) {
            T = C[i]; C[i] = C[j]; C[j] = T;
            i++; j--;
        }
    }
    if(l < j) Hoar(C, l, j);
    if(i < k) Hoar(C, i, k);
}

это мое старое из универа, можешь сравнить тута.

а это битовая сортировка:

void Bit(int C[], int l, int k, int X)
{
    int  i = l, j = k, T;

    while(i <= j) {
        while(!(C[i] & X) && i <= j) i++;
        while( (C[j] & X) && i <= j) j--;
        if(i <= j) {
            T = C[i]; C[i] = C[j]; C[j] = T;
            i++; j--;
        }
    }
    if(X >>= 1) {
        if(l < j) Bit(C, l, j, X);
        if(i < k) Bit(C, i, k, X);
    }
}

опять же с универа.

Смотри внимательнее — жирным ВСЕ ОСНОВНЫЕ ОТЛИЧИЯ АЛГОРИТМОА!!!

Или нас всех дружно 5 лет обманывали???
Ну и где здесь различия в глубине рекурсии???
Можешь ткнуть меня носом, если найдешь!

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

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

cpp>>Я вот тут почитал соседние ветки и задумался.
cpp>>Господин Atilla, здесь что все серьезно уверены, что асимптотическая скорость Вашего алгоритма O(n)???

A>а Вы серьезно уверены, что асимптотическая сложность этого алгоритма O(N*log2(N)) ???

A>Ну сами подумайте: глубина рекурсии ограничена числом sizeof(value_type)*8 ! На каждой глубине сравнений (или битовых and'ов) может быть N или немного меньше. Итого сравнений примерно 32*N (для unsigned long'ов). У qsort'а же глубина рекурсии может доходить до N! ну а в лучшем случае — log2(N), поэтому и получается такая асимптотика. Другое дело что в большинстве случаев log2(N) < 32 но это уже к асимптотике не имеет отношения

Сразу извиняюсь, прости меня Atilla! что так резко отвечал, просто сортировки оченя долго изулали.
A> Другое дело что в большинстве случаев log2(N) < 32

да, но где столько взять!
с остальным согласен...
еще раз сорри.

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

cpp>>Я вот тут почитал соседние ветки и задумался.
cpp>>Господин Atilla, здесь что все серьезно уверены, что асимптотическая скорость Вашего алгоритма O(n)???

A>а Вы серьезно уверены, что асимптотическая сложность этого алгоритма O(N*log2(N)) ???

A>Ну сами подумайте: глубина рекурсии ограничена числом sizeof(value_type)*8 ! На каждой глубине сравнений (или битовых and'ов) может быть N или немного меньше. Итого сравнений примерно 32*N (для unsigned long'ов). У qsort'а же глубина рекурсии может доходить до N! ну а в лучшем случае — log2(N), поэтому и получается такая асимптотика. Другое дело что в большинстве случаев log2(N) < 32 но это уже к асимптотике не имеет отношения

А что такое 32?! Это -- число бит.
А что такое число бит? Это, елы-палы, log2(ULONG_MAX).
Поэтому O(N*32) >= O(N*log2(N)), если числа уникальны

Что же касается асимптотики — то есть другие сортировки, например, heapsort — которые гарантируют скорость и глубину, в отличие от qsort.
Наконец, можно модифицировать qsort (к примеру, рандомизировать массив), чтобы улучшить его характеристики.

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

К>А что такое 32?! Это -- число бит.
К>А что такое число бит? Это, елы-палы, log2(ULONG_MAX).
К>Поэтому O(N*32) >= O(N*log2(N)), если числа уникальны

К>Что же касается асимптотики — то есть другие сортировки, например, heapsort — которые гарантируют скорость и глубину, в отличие от qsort.
К>Наконец, можно модифицировать qsort (к примеру, рандомизировать массив), чтобы улучшить его характеристики.

Да понимаю я все это Просто формально, сложность алгоритма O(N) и тут уж ни к чему не придерешься.
Чем еще хорош этот алгоритм, так это тем, что является примером, когда алгоритм быстрый в асимптотике на практике работает медленнее алгоритмов с более медленной асимптотикой. Обычно бытует мнение, что O(N) это лучше чем O(N*log(N)), который лучше чем O(N^2), и это утверждение легко опровергается моим "велосипедом"

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

cpp>Сразу извиняюсь, прости меня Atilla! что так резко отвечал, просто сортировки оченя долго изулали.

Да ничего, со всеми бывает

A>> Другое дело что в большинстве случаев log2(N) < 32
cpp>
cpp>да, но где столько взять!

ну на самом деле ненавороченный qsort дает в среднем глубину рекурсии 1.5*log2(N) (у heap_sort в сумме больше операций получается, чем у qsort), навороченный меньше, но все равно не log2(N). Т.е. в принципе битовая сортировка должна приближаться (и приближается) к qsort уже на миллионных массивах. А при N>=1E+9 должна уже обгонять.
Учитывая, что еще 10 лет назад массивы в 100 мегабайт были фантастикой.....