JavaScript - Сортировка массива с помощью функции

По умолчанию метод sort сортирует массив в алфавитном порядке, для этого он представляет каждое значение элемента массива как строку с помощью метода toString()
.
Например, сортировка массива, состоящего из чисел:
var arrNumbers = new Array (50,4,1,76,20,3,27,5,501); document.write("Исходный массив:"); document.write("<br>"); document.write(arrNumbers.join(", ")); document.write("<br>"); arrNumbers.sort(); document.write("Отсортированный массив:"); document.write("<br>"); document.write(arrNumbers.join(", "));
Чтобы отсортировать массив так, как мы хотим, нам необходимо написать специальную функцию и передать её имя в качестве параметра методу sort
.
Но перед тем как перейти к созданию функции, давайте рассмотрим алгоритм, с помощью которого метод sort
упорядочивает массив. На самом деле алгоритм сортировки очень прост и заключается в многократном сравнении 2 рядом расположенных элементов в массиве, которые в зависимости от результата сравнения переставляются (упорядочиваются).
Следовательно, специальная функция должно иметь 2 параметра. Причём передавать значения этих параметров будет сам метод sort
, т.е. значения параметров нам не известны. А для нас это и не важно, т.к. наша задача сводится к написанию алгоритма сравнения значений этих параметров и выдаче в качестве результата значения, по которому метод sort
будет определять, переставлять эти элементы массива или нет.
Т.е. метод sort определяет, переставлять элементы или нет в зависимости от результата, которая возвращает данная функция. Рассмотрим, какие значения должна возвращать функция:
- Если функция возвращает 0, то данные элементы массива равны;
- Если функция возвращает 1 (или больше 0), то это означает что первый элемент массива больше второго;
- Если функция возвращает -1 (или меньше 0), то это означает что второй элемент массива больше первого.
После создания функции, её необходимо передать в качестве параметра методу sort
. Причём передавать необходимо только название этой функции, без заключения её в кавычки и без указания круглых скобочек. Это всё объясняется тем, что мы не просим метод sort
вызвать эту функцию прямо сейчас, а просто сообщаем данному методу, чтоб он именно её использовал при сравнении элементов массива, т.е. как бы подменяем его стандартную функцию для сортировки массива на функцию, заданную ему в качестве параметра.
Например, напишем функцию для сортировки чисел:
//Функция для сравнения чисел, которая возвращает: // 0 - числа равны; // 1 - первое число больше второго числа // -1 - второе число больше первого числа function compareNumbers(n1,n2) { if (n1==n2) return 0; if (n1>n2) return 1; else return -1; } var arrNumbers = new Array (50,4,1,76,20,3,27,5,501); document.write("Исходный массив:"); document.write("<br>"); document.write(arrNumbers.join(", ")); document.write("<br>"); arrNumbers.sort(compareNumbers); document.write("Отсортированный массив:"); document.write("<br>"); document.write(arrNumbers.join(", "));
Таким образом, используя специальную функцию, Вы можете заставить метод sort
отсортировать массив по указанному в данной функции алгоритму.
Например, сортировка числового массива в обратном порядке:
//Функция для сравнения чисел, которая возвращает: // 0 - числа равны; // 1 - первое число больше второго числа // -1 - второе число больше первого числа function compareNumbers(n1,n2) { if (n1==n2) return 0; if (n1<n2) return 1; else return -1; } var arrNumbers = new Array (50,4,1,76,20,3,27,5,501); document.write("Исходный массив:"); document.write("<br>"); document.write(arrNumbers.join(", ")); document.write("<br>"); arrNumbers.sort(compareNumbers); document.write("Отсортированный массив:"); document.write("<br>"); document.write(arrNumbers.join(", "));
Принцип алгоритма быстрой сортировки заключается в следующем. Сначала выбирается опорный элемент (например, средний). После этого элементы слева и справа от него сравниваются с ним. Если какой-то элемент слева больше опорного, то он перемещается вправо. То же самое качается и элементов справа от него, но действие выполняются наоборот. Т.е. если элемент меньше опорного, то он перемещается влево. В итоге после этих манипуляций получится 2 разделённых массива. В первом массиве (слева от опорного) будут находиться элементы меньше опорного. А во втором (справа от опорного) будут находиться элементы больше опорного. Потом все действия повторяются сначала. Т.е. берётся массив слева от опорного элемента и в нём выполняется всё то же самое. Т.е. определяется опорный элемент, а другие перемещаются относительно него. Все эти действия повторяются рекурсивно, пока массив не будет отсортирован. Т.е. пока не останутся куски массивов, которые уже нельзя делить. Потом всё соединяется, и вы получаете отсортированный массив.
Вам необязательно знать принцип работы алгоритмов, достаточно указать условие, по которому одни элементы перемещать вправо, а другие влево. Для этого и нужна функция с двумя параметрами. В ней Вы должны указать условие, по которому JacaScript будут одни элементы перемещать вправо (>1) или влево (<1).
Например:
Если необходимо его отсортировать как числа, то необходимо создать дополнительную функцию и указать её в качестве параметра метода sort: