про метод sort()
 

Доброго времени суток! В библии пользователя(Гудман) и подробном руководстве(носорог) по javascript действие метода sort() массива разъясняется так: берется две соседних ячейки и сравниваются. Но в таком масиве [4,5,6,3] каким образом тройка станет вперед, ведь она никак не является соседней для четверки? И еще при использовании аргумента-функции, результатом которой является 1,-1или 0 почему в подробном руководстве говорится, что данная функция запустится всего одлин раз, ведь она должна запускатся при каждом сравнении пар значений?

При сортировке используется алгоритм быстрой сортировки, при котором сравниваются не все пары чисел. Callback-функция будет вызвана не один раз.

А по подробнее про алгоритм?
 

А по подробнее про алгоритм?

Не везде.
V8: qsort с выбором опоры как среднего из трех и переходом на сортировку вставками для массивов размером меньше 10 (array.js:678).

Spidernonkey: mergesort (jsarray.c:1962).

JavaScriptCore: в коде есть такой комментарий: (ArrayPrototype.cpp:506)
Как я понял, это сортировка выбором.

Увы, но про Carakan и Charka ничего сказать не могу :-(

Т.е. сам sort вызывает эту функцию много (сколько нужно) раз? А программисту достаточно указать один раз sort(foo())?

Вот что сам Флэнэган пишет по этому поводу:

"Для сортировки в какомлибо ином порядке, отличном от алфавитного, можно
передать методу sort() в качестве аргумента функцию сравнения. Эта функция
устанавливает, какой из двух ее аргументов должен присутствовать раньше в от
сортированном списке. Если первый аргумент должен предшествовать второму,
функция сравнения возвращает отрицательное число. Если первый аргумент
в отсортированном массиве должен следовать за вторым, то функция возвращает число, большее нуля. А если два значения эквивалентны (т. е. порядок их рас
положения не важен), функция сравнения возвращает 0."

var a = [33, 4, 1111, 222];
a.sort(); // Алфавитный порядок: 1111, 222, 33, 4
a.sort(function(a,b) { // Числовой порядок: 4, 33, 222, 1111
return a-b; // Возвращает значение < 0, 0, или > 0
}); // в зависимости от порядка сортировки a и b

Откуда тут вообще взялись a и b? Они же нигде явно не определялись.
Понятно, что они как то берутся из массива, но как?

они передаются функцией sort в callback
то есть когда функция сортировки сранивает два элемента, чтобы определить какой из них должен идти раньше, она вызывает колбек

Gvozd,
ух-ты!
Первый раз вижу, чтоб вызывающая функция (sort) передавала (задавала) функции-аргументу (foo()) аргументы...
Алгоритм конечно замысловатый... :blink:

JSTalker,
у вас сильные пробелы в базовых знаниях

function func1(funcname, funcparam){
funcname(funcparam);
}
func1(alert,'olo-lo');

JSTalker,
скобочки-то лишние уберите уже наконец.

sort(foo); // а не sort(foo())

вы вообще не о том.
Kolyaj
почему лишние? Это не функциональный литерал (там как бы аргументы подразумеваются).

просьба своим языком объяснить этот алгоритм

И как он применяется в JS. А то я что то допереть никак ни могу

вся соль разделения массива заключается в подчеркнутой строчке?

Алгоритм 2.N выполняется только 1 раз для целого массива? Далее он выполняется для левых и правых подмассивов?

Как все это с sort(foo(a,b)) в JS стыкуется?
a,b - это что за элементы относительно вышеописанного?
просто любые 2 элемента, а в функции показано условие?

Потому что вызываете функцию foo и результат её выполнения передаёте в sort. А нужно передавать в sort саму функцию foo, а не результат её выполнения.

Какая вам разница, как реализована сортировка в JS?

это элементы которые сравниваюстя между собой
2.3 и 2.4 содержат операции сравнения элементов(не индексов)

Что за вопросы?
Большая.

О примере JStalkera
 

Не могу понять логику действий:
-почему у массива нельзя найти медиану(я понимаю середину массива) у любого массива (объект.constructor==Array) есть свойвство length; или обсуждение вышло за рамки метда sort()?
- подчеркнутого пункта - когда проверяется условие I<r (здесь сравнивается значение элемента, а не индексы, иначе нет смысла в слепую менять значения, ориенируясь только на их индексы в массиве.), я думаю проверяется при каждой итерации п.2.3 и п.2.4 (как указал Gvozd).

Почитал-почитал, и всё-таки не могу понять этот sort. Например, какую ф-ию передавать ему, если я хочу убрать из массива все элементы со значением undefined.

Раед,
Если Вы хотите _убрать_ из массива элементы, причем здесь _сортировка_ массива?

Ну если вы отсортируете массив, то все такие элементы окажутся в конце. Удалять потом, конечно, будет проще- НО ЗАЧЕМ?

Как зачем? В массиве есть несколько элементов, иногда они из него удаляются, и я хочу, чтобы при удалении все остальные элементы сдвигались. Сделал так:

var arr=[5,8,7,65,64,842,8,42,8,41,6,8,777];
alert(arr.length);
delete arr[4];
delete arr[6];
delete arr[1];
arr = arr.sort(function(a,b){return (b==undefined ? -1 : 0)});
alert(arr.length);
var x = arr.length;
while (arr[--x]==undefined) arr.pop();
alert(arr.length);

Раед, значения undefined в твою функцию сортировки даже не будут переданы, ибо сортируются всегда отдельно.
Во вторых, прямой обход массива -это порядок n. Сравни с сортировкой, которая O(n log n), хотя тут вообще порядок будет n, так как ничего по сути не сортируется + вызовы функции.
Это что? Оптимизация?

Медиана != Середина массива.
Медиана = середина распределения частот. Лучше всего подходит для характеристики расположения центра распределения для интервальной или относительной шкалы.
Хороший график для понимания:

или


На сколько адекватна будет медиана для такого массива?: [15, "d", 1, "a", 4, "b"]. Кстати стандартный метод, числовую часть сортирует неправильно -> 1,15,4,a,b,d

Из этих слов не понял ровным счётом ничего :-?

это как, а почему же тогда всё работает?

Твоя функция сортировки всегда возвращает 0, т.е. эквивалентность для сортировки, поскольку в function(a,b){return (b==undefined ? -1 : 0)}
undefined сюда не передаются никогда-так уж сортировка устроена в js(да и не только в js, кстати).
Поскольку она утверждает, что все неважно, функция вызывается ровно n-1 раз.

Rootpassword,
Во первых, что такое n
Во вторых, то что undefined в ф-ию не попадают, это я уже понял. Но почему же они оказываются в конце массива?

n, N-всегда количество данных.

Потому что сортируются отдельно, без функции, и записываются в конец. Все !undefined сортируются функцией, и потом все undefined просто добавляются в конец массива.

То есть можно просто:

arr.sort()

вау!