Сортировка в ширину
 

Доброго времени суток... Приспичило меня (просто ради интереса) сравнить скорость работы сортировки в ширину с сортировкой быстрой. Причём решил сделать это в firebug-е...

Код следующий:

console.clear();

// Формирование массива

var w = 10 * 1000; // разброс значений
var h = 400 * 1000; // количество элементов
var a = new Array(h); // массив

console.time('Make array');
for( var i = 0; i < h; ++i )
{
    a[i] = Math.floor(Math.random() * w);
}
console.timeEnd('Make array');

// Cортировка "в ширину"

console.time('WideSort');
var b = new Array(w);
var c = new Array(h);

for( i = 0; i < h; ++i )
{
    if( !b[ a[i] ] )
        b[ a[i] ] = 1;
    else 
        ++b[ a[i] ];
}

var z = -1;
for( i = 0; i < w; ++i )
{
    for( var t = 0; t < b[i]; ++t )
    {
        z++;
        c[z] = i;
    }
}
console.timeEnd('WideSort');

// Быстрая сортировка

console.time('QuickSort');
function qsort( mas, f, t )
{
    var l = f, r = t;
    var middle = Math.floor( (t + f)/ 2 );
    var m = mas[ middle ];

    do {
        while( mas[l] < m ) ++l; // находим первый слева элемент больший центрального
        while( mas[r] > m ) --r; // находим первый правый элемент меньший центрального

        if( l <= r ) { // меняем местами больший чем М элемент слева, с меньшим чем М,
            var temp = mas[l]; // элементом справа
            mas[l] = mas[r];
            mas[r] = temp;
            ++l; --r;
        }
    } while ( r >= l ); // пока не кончится отрезок массива

    if( f < r ) qsort( mas, f, r );
    if( t > l ) qsort( mas, l, t );
}
qsort( a, 0, a.length - 1 );
console.timeEnd('QuickSort');


// Проверка
for( i = 0; i < h; ++i )
    if( a[i] != c[i] )
    {
        console.log('a[i] = ',a[i],' c[i] = ',c[i]);
        break;
    }

Результат ужасен, сортировка в ширину у меня всегда проигрывает, какие бы я исходные данные не ставил. Проверил тоже в Delphi, там ситуация более идеологически верная - быстрая сортировка медленнее примерно в 10 раз, вплоть до увеличения h до 2-3 миллионов.

Можно ли в Js вернуть "справедливость"? :) Насколько я понимаю, всё дело в медленном создании массива...

P.S. Я в js совсем "зелёный" :)

#upd

Chrome:

:)

по-моему все в порядке.
проверь фаербагом так ли это

Что же тут нормального :) Вот нормальный результат для 50лямов в Delphi:
Найти причину проблемы не смог =( Кроется она в строчке после else:

for( i = 0; i < h; ++i ) 
{
    var p = a[i]; 
    if( !b[ p ] ) 
        b[ p ] = 1; 
    else 
        ++b[ p ]; 
}

это недоразумение.
связанно может быть с тем, что в Delphi слишком больше накладные расходы на вызов функции, или еще с чем-то.
Почитайте про сложность алгоритмов, и подумайте как от сложности зависит скорость. только хорошо подумайте.

PS Откуда вы взяли вообще такое дивное название "сортировка в ширину".
гугл выдает в первую очередь эту тему)
PPS *тут должно было быть что-то нехорошее про Delphi. Но может быть и ваша реклама*.

Это закономерность )

Gvozd, вот - http://acmp.ru/index.asp?main=solution&id_task=41 . Называется она правда иначе (цифровая сортировка), но суть от этого не меняется. qSort-ом, насколько я помню, ту задачу не решить, по времени не укладывается :) Хотя если применить какую нидь шаманскую си магию...

Вы про это?
Я полагаю, что сложность там не O(N), а более запутанная, и выводить мне её лень, никогда эти О() не любил...

Запустил ваш пример (Firefox 3.6)

Kolyaj, о_О... unix-версия? У меня 3.6.15 (win32) выдаёт:

WinXP.

В коде из первого сообщения ничего не менял.