Сортировка массива

Сортировка — это одна из самых важных и трудноразрешимых проблем в программировании. Нередко потребность в перераспределении элементов в массиве исходя из возрастания или убывания того или иного свойства возникает и при создании алгоритмов на ActionScrip. Однако знать тонкие методы сортировки совсем необязательно, так как язык программирования Flash имеет достаточно мощные встроенные возможности для решения подобных задач.

Наиболее общим инструментом сортировки массивов является метод sort(). Его синтаксис:

array, sort (comparefn),
где:

• array — массив, подлежащий сортировке;
• comparefn — функция, определяющая, при соблюдении каких условий один элемент должен располагаться в массиве раньше, чем другой. Правила ее задания:

o comparefn должна приниматьдва параметра, для определенности назовем их х и y;
o если х оказывается большим у, comparefn должна возвратить 1;
o если х оказывается меньшим у, comparefn должна возвратить -1;
o если х равен у, то comparefn должна возвратить 0.

На первый взгляд, синтаксис метода sort() кажется очень сложным. Однако вы без зуда в нем разберетесь, проанализировав следующий пример:

// Сортируем массив из чисел по возрастанию
arr:Array = [3, 2, 4, 1, 5, 0]; // Неотсортированный массив
function mySort(x:Number, y:Number):Number { // Функция сортировки
if (x>y) {
return 1; // Если одно из чисел больше другого,
// оно перемещается к концу массива
if (x return -1;
if (x = у) {
return 0; // Если числа одинаковы, никаких изменений не произойдет
}
}
arr.sort(mySort);
trace(arr); // Выводит: 0, 1, 2, 3, 4, 5

Если какой-то из элементов массива не определен (т.


е. при его вызове возвращайся undefined), то он будет расположен в конце полученной в результате сортировки иерархии элементов:

var arrrArray = [3, 2, 4,undefined, 1, 5, 0];
аrr.sort(mySort); // Результат: undefined, 0, 1, 2, 3, 4, 5
функция сортировки может возвращать методу sort() не только 1, —1 или 0, но и любое число.

При этом отрицательное значение будет трактоваться так же, как и — 1, а положительное — так же, как и 1. Зная это, зачастую можно существенно сокращать код функции сортировки. Например, скрипт функции mySort может быть уменьшен всего до одной строчки:

var arr:Array = [3, 2, 4, 1, 5, 0];
function mySort(x:Number, y:Number):Number {
return x-y;
}
arr.sort(mySort);
trace(arr); // Выводит: 0, 1, 2, 3, 4, 5

Параметр comparefn метода sort() не является обязательным. Если он не задан, то при сортировке элементы массива преобразуются в строки и распределяются исходя из возрастания Unicode-кодов символов, их образующих (подробно принципы сравнения строк описаны в главе 5). Если все символы принадлежат к одному алфавшу и заданы в одном регистре, то подобный упрощенный синтаксис метода sort() может быть использован для сортировки по алфавиту:

var arr:Arrау=["яблоко", "ананас", "дыня","груша"];
arr.sort();
trace (arr); // Выводит: ананас, груша, дыня, яблоко

Так как одна и та же буква, но в разных регистрах, задается различными символами, то для того, чтобы организовать качественную сортировку строк, нужно использовать методы toLowerCase() или toUpperCase() класса String, приводящие буквы строки к одному регистру:

// Названия фруктов начинаются буквами в разных регистрах
var arr:Array = ["яблоко", "Ананас", "Дыня", "груша"];
arr.sort(); // Сортируем элементы с учетом регистра
trace(arr); // Выводит: Ананас, Дыня, груша, яблоко (неиерный порядок)
function mySort(x:String, y:String):Boolean {
return x.toLowerCase()>y.toLowercase();
}
arr.sort(mySort); // Сортируем без учета регистра
trace(arr); // Выводит: Аканас, груша, Дыня, яблоко

Во Flash MX 2004 наиболее важные настройки сортировки могут быть проведены без задания соответствующего элемента в коде сортирующей функции.


Для этого в качестве параметра методу sort() должна быть передана одна из констант, которые хранятся в специальных свойствах конструктора Array:

• Array.CASEINSENSIT1VE (или 1). Сортировка по алфавиту без учета регистра. Позволяет проводить качественную сортировку строк без создания сортирующей функции и обращения к методам toLowerCase() и toUpperCase() класса String. Например:

var arr:Array = ["яблоко", "Ананас", "Дыня", "груша"];
arr.sort(Array.CASEINSENSITIVE); // Сортируем элементы без учета регистра
trace(arr); // Выводит: Ананас, груша. Дыня, яблоко

• Array.DESCENDING (или 2). Сортировка в обратном направлении по сравнению с принятой по умолчанию. В частности, данная настройка может быть использована, если числа должны быть отсортированы не по возрастанию, а по убыванию. Впрочем, возможны и более изощренные варианты сортировки:

var arr:Array = ["яблоко", "ананас", "дыня", "груша"];
arr.sort(Array.DESCENDING); // Сортируем элементы в порядке,
// обратном алфавитному
trace (arr); // Выводит: яблоко,дыня,груша,ананас

• Array.UNIQUESORT (или 4). Если окажется, что признак, исходя из которого проводится сортировка, одинаков у двух элементов, метод sort() возвратит 0, а сам массив отсортирован не будет.


Например:

var arr:Array = ["яблоко", "ананас", "дыня", "груша", "яблоко"];
trace(arr.sort(Array.UNIQUESORT)); // Возвращает 0 [элемент "яблоко"
// встречается дважды!
trace(arr); // Выбодит: яблоко, ананас, дыня, груша, яблоко
// (массив отсортирован не был)

• Array.RETURNINDEXEDARRAY (или 8). Результат сортировки будет возвращен как самостоятельный массив, элементы которого будут отображать результат сортировки, т. е. в них будут храниться не значения элементов, а лишь их индексы. Исходный массив при этом изменен не будет. Например:

var arr:Array = ["яблоко", "ананас", "дыня", "груша"];
trace(arr.sort(Array.RETURNINDEXEDARRAY)); // Выводит: 1, 3, 2, 0
// (в таком порядке должны быть расположены
// элементы отсортированного массива)
trace(arr); // Выводит: яблоко, ананас, дыня, груша (массив
// отсортирован не был)

• Array.NUMERIC (или 16). Параметр задает сортировку чисел по возрастанию. | Пожалуй, наиболее важный для практики параметр сортировки. Пример:

var arr:Array = [1, -23, 78, 0, 4.89, Number.MAX VALUE,
Number.NEGATIVE_INFINITY];
arr.sort(Array.NUMERIC); // Сортируем массив чисел по возрастанию
trace(arr); // Выводит: -Infinity, -23, 0, 1, 4.89, 78,
// l.79769313486231e+308

Одновременно можно использовать несколько параметров сортировки. Для этого Их значения должны быть слиты в одно целое число при помощи оператора побитового логического ИЛИ «|».

Для примера приведем код, сортирующий массив чисел по убыванию (чтобы добиться такого результата, нужно совместить параметр сортировки чисел по возрастанию NUMERIC и параметр сортировки в обратном порядке DESCENDING)

var arr:Array=[l, -23, 78, 0, 4.89, Number.MAX VALUE,
Number.NEGATIVE_INFINITY];
arr.sort(Array.NUMERIC|Array.DESCENDING);
trace(arr); // Выводит: 1.79769313486231e+308, 78, 4.89, 1, 0, -23,
// -Infinity

Если вы прочитали раздел, посвященный побитовым операторам, вам будет абсолютно ясно, в чем смысл применения оператора «|» для совмещения нескольких параметров сортировки. Дело в том, что все настройки сортировки должны быть переданы методу sort() в виде одного целого числа. За каждую опцию отвечает отдельный бит этого числа: если он равен I, она активна, если же ему соответствует 0, то настройка не действует.

Значением рассмотренных выше свойств конструктора Array являются целые числа, у которых только один, занимающий соответствующую опции позицию, бит равен 1. Применяя к таким числам оператор побитового логического ИЛИ, вы создаете число, у которого установлены (равны 1) уже два бита, расположенные на тех же позициях, что и
установленные биты у операндов.

Например:
// Объединяем настройку UNIQUESORT (4 — двоичное 100) и настройку
// RETURNINDEXEDARRAY (6 - двоичное 1000)
trace((Array.UNIQUESORT|Array.RETURNINDEXEDARRAY)) // Выводит: 12
trace((12).toString(2)); // Выводит: 1100 (установлены два бита —
// действуют пве настройки)
// Проведенная выше операция может быть записана и более явно
trace((parseInt ("100",2] parseInt ("1000",2]).toString(2)); // Выводит: 1100

Когда метод sort() получает параметр настроек сортировки, он анализирует его на предмет установленных битов (их часто называют флагами). Опции, флаги которых равны 1, активизируются.

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

Опции сортировки не описаны в ЕСМА-262 и являются особенностью ActionScript (например, JavaScript они не поддерживаются).

Во Flash MX появился новый метод сортировки, не описанный в спецификации ЕСМА-262, — sortOn().

Данный метод позволяет отсортировать элементы массива по возрастанию какого-то из их свойств. Естественно, что все они должны быть объектами.

Синтаксис метода sortOn():

Array.sortOn ("property"),
где:

• Array — подлежащий сортировке массив, элементами которого являются объекты;
• "property" — строка с именем свойства, исходя из возрастания которого должна проводиться сортировка.

Если элементы массива не имеют свойства property, то они будут отсортированы по тому же алгоритму, что использует метод sort().

Пример:
var arr:Array = [{pr:"C"), (pr:"A"}, {pr:"B"}]; // Массив содержит три
// объекта со свойством pr
arr.sortOn("pr");
for (var i = 0; i trace(arr[i].pr); // Выводит: А, В, С
}

Метод sortOn(), как и метод sort(), может использовать параметры сортировки. Например:

var arr:Array = [{pr:"C"}, {pr:"A"}, {pr:"B")];
// Проводим сортировку в обратном порядке:
arr.sortOn("pr", Array.DESCENDING);
for [var i = 0; i trace(arr[i].pr); // Выводит: С, В, А I
}

Метод sortOn() является достаточно «сырым», и при его использовании могут возникать разного рода неожиданности. Поэтому надежнее во всех случаях применять метод sort().

Оцените статью: (0 голосов)
0 5 0

Статьи из раздела Action Script на эту тему:
Выделение фрагмента массива
Длина массива. Свойство length
Добавление элементов в массив
Извлечение и переопределение элементов массива
Инверсия массива

Вернуться в раздел: Action Script / 7. Массивы (класс Array)