Javascript-форум - про метод sort()

Javascript-форум (https://javascript.ru/forum/)

- Элементы интерфейса (https://javascript.ru/forum/dom-window/)

- - про метод sort() (https://javascript.ru/forum/dom-window/14102-pro-metod-sort.html)

Цитата:

Сообщение от Gvozd (Сообщение 86550)

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

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

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

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

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

Цитата:

Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:
1. Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом.
2. Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него. Обычный алгоритм операции:
2.1 Два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива соответственно.
2.2 Вычисляется индекс опорного элемента m. (??? а п.1 что делал?)
2.3 Индекс l последовательно увеличивается до m до тех пор, пока l-й элемент не превысит опорный.
2.4 Индекс r последовательно уменьшается до m до тех пор, пока r-й элемент не окажется меньше либо равен опорному.
2.5 Если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент.
2.6 Если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно.
3. Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.
4. Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения.

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

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

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

Цитата:

Сообщение от JSTalker

почему лишние?

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

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

Цитата:

Сообщение от JSTalker

a,b - это что за элементы относительно вышеописанного?

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

Цитата:

Сообщение от Kolyaj (Сообщение 86585)

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

О примере JStalkera

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

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

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

Цитата:

Сообщение от Раед

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