Сортируем массив чисел клиентским JavaScript

Jazz

Опубликован:	2024-01-07T07:42:34.231761Z
Отредактирован:	2024-01-07T07:42:34.231761Z
Статус:	публичный

Jazz блог

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

Условия задачи

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

В самом общем случае решить эту задачу можно с любым современным языком программирования. Для этого обзора я выбрал JavaScript. Его интерпретатором можно воспользоваться для решения предложенной задачи, а само решение показать в самом обычном современном браузере, например, Chromium.

Подготовка

Для решения задачи мне потребуется текстовый редактор и Интернет браузер. Чтобы сохранить решение "на бумаге", создаю простой текстовый файл с именем index.html.

vim index.html

В этот файл пишу самый простой начальный html-код следующего содержания:

<!DOCTYPE html>
<html lang="ru">
  <head>
    <meta charset="utf-8">
    <title>JavaScript, сортируем массив чисел</title>
  </head>
  <body>
    <div>JavaScript посиделки.</div>
  </body>
</html>

Вот так это выглядит на моём десктопе.

Запускаю браузер Chromium и открываю только что созданный html-файл. Чтобы не возить по экрану монитора курсор мыши, сделать это проще всего текстовой командой.

chromium file:///home/newbie/index.html

Жму ОК. Запустится Chromium, в его окне запускаю с помощью клавиатурного сочетания crtl+shift+i инструменты разработчика. Окно браузера поделится на две части, перемещаюсь во второй части окна на вкладку Console.

Таким образом в моём распоряжении оказалась интерактивная консоль встроенного в браузер интерпретатора языка программирования JavaScript. У меня есть окружение, можно приступить к решению поставленной задачи в нём.

Инициализация исходного массива

Естественно, чтобы что-то отсортировать, это что-то для начала нужно иметь. Это значит, что мне необходим массив, содержащий целые числа, следующие в случайном порядке. Можно такой массив "состряпать" от руки и набить вероятную последовательность целых чисел, но это хлопотно, поэтому я попрошу компьютер создать искомый массив, который станет исходным для решения основной задачи. Давайте разберёмся, как это можно сделать стандартными средствами.

В браузерном JavaScript, такой обычно называют JavaScript Client Side, есть специальный, стандартный, библиотечный объект Math. В этом объекте заключена вся элементарная математика и средства для вычислений. В составе этого объекта имеется метод Math.random, вызовом которого мы получим случайное число. Вбиваю в приглашение интерпретатора в консоли браузера такую простую строчку.

> Math.random();

Интерпретатор отзовётся и выведет случайное число. Дабы убедиться, что число действительно случайное, можно повторить этот же вызов ещё раз.

Как мы видим в ответе интерпретатора на повторный вызов число не совпало с ответом интерпретатора в предыдущем вызове, делаю вывод, вызов возвращает случайное число.

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

Math.round(Math.random() * 99 + 1);

Опять ввожу эту строчку в консоли браузера пару раз. И вот как интерпретатор откликается на этот вызов.

Повторив этот вызов любое количество раз, я могу получить случайное целое число в заданном интервале это количество раз. Чтобы не писать каждый раз это выражение, в нём слишком много букв, напишу простую функцию, которая реализует заполнение массива. Возвращаюсь в текстовый редактор и пишу внутри тега <body> следующий код.

<script>
  // Создаём функцию с именем setA
  // В аргументах функции задаю имя и длину массива
  function setA(ar, len) {
    // в теле функции выполняю заданное количество повторений
    // с помощью стандартного цикла for
    for (let i = 0; i < len; i++) {
      // и повторять я буду только что разработанную формулу
      // а полученное в результате вычислений значение
      // сохраню как элемент массива с соответствующим индексом.
      ar[i] = Math.round(Math.random() * 99 + 1);
    }
  }
</script>

Вот как этот код выглядит в окне моего текстового редактора.

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

Сохраняю изменения в файл и возвращаюсь в окно браузера. Обновляю страницу кнопочкой с круговой стрелкой, жму её. Теперь на этой странице я могу совершенно без труда получить искомый массив из случайных целых чисел. Допустим, мне нужен массив из 22 элементов, пишу в консоли браузера пару-тройку вызовов.

// создаю пустой массив с именем target
> let target = new Array();
// заполняю этот массив данными
> setA(target, 22);
// посмотрим на результат усилий
> console.log(target);

И вот как на эти вызовы мне ответит интерпретатор.

Массив создан. Подготовку к решению основной задачи можно считать законченной. Все необходимые для демонстрации инструменты я создал.

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

Алгоритмы сортировки известны и разработаны ещё на заре формирования компьютерной науки. Известно несколько вариантов алгоритмов сортировки. В рамках этого обзора я покажу один единственный алгоритм - сортировку вставками. И вот как этот алгоритм выглядит в терминах JavaScript.

// мне потребуется переменная для обмена, дам ей имя box
> let box;
// при помощи стандартного цикла for
// делю исходную последовательность на две
// 1. неотсортированная последовательность
// 2. отсортированная последовательность
// неотсортированная последовательность начинается с первого элемента
// и продолжается до последнего элемента исходного массива
// отсортированная последовательность на первой итерации
// включает только нулевой элемент
> for (let i = 1; i < target.length; i++) {
     // сохраняем значение текущего элемента массива
     // в переменной box
     box = target[i];
     // чтобы задать границу отсортированной последовательноси
     // мне потребуется ещё одна переменная - j
     let j = i - 1;
     // значение этой переменной равно индексу
     // последнего элемента в отсортированной последовательности
     // для каждого элемента отсортированной последовательности
     // сравниваем текущие значения
     while (j >= 0 && box < target[j]) {
       // если условие выполняется, выполняем первый обмен значений
       target[j+1] = target[j];
       // меняем текущий индекс
       j -= 1;
     }
     // после завершения вложенного цикла
     // выполняем второй обмен значений
     target[j+1] = box;
   }

Всё. Массив отсортирован по возрастанию. Давайте посмотрим на него.

> console.log(target);

Вот что получилось у меня в итоге в окне браузера.

Алгоритм содержит два цикла, основной и вложенный. Действия вложенного цикла всегда сложно отлаживать, поэтому решение задачи обычно даётся начинающим программистам не с первого раза. Но, поскольку алгоритм является типовым, его можно просто вызубрить перед собеседованием или экзаменом. Вкупе с пониманием, как алгоритм работает, мышечная моторика поможет напечатать решение не думая, когда это потребуется.

Закрепляем решение

Рабочее решение неплохо бы сохранить. Для этого возвращаюсь в окно текстового редактора и дописываю в скрипт файла index.html ещё одну функцию.

function sortAr(ar) {
  let box, i, j;
  for (i = 1; i < ar.length; i++) {
    box = ar[i];
    j = i - 1;
    while (j >= 0 && box < ar[j]) {
      ar[j+1] = ar[j];
      j -= 1;
    }
    ar[j+1] = box;
  }
}

Сохраняю изменения в файл, возвращаюсь в браузер, обновляю страницу и повторяю решение задачи несколькими простыми вызовами в консоли браузера. Функция JavaScript - великолепное средство для повторяющихся действий.

> let target = new Array();
> setA(target, 88);
> sortAr(target);
> console.log(target);

И вот что мне показывает браузер в своём окне в итоге.

Как видно на крайнем нижнем снимке экрана, предложенное решение вполне справляется с поставленной задачей. Я создал пустой массив. Заполнил его с помощью вызова функции setA, она позволяет задать длину получаемого массива. Полученный массив передал в качестве параметра функции sortAr и попросил интерпретатор напечатать полученный массив. Значения элементов массива следуют в заданном условиями задачи направлении, массив отсортирован по возрастанию. Задача решена, и решение продемонстрировано тестовыми вызовами в интерактивной сесси интерпретатора JavaScript.

Выводы

Браузерный JavaScript является полноценным языком программирования, и, благодаря его возможностям, браузер можно использовать нецелевым образом, например как обычный калькулятор или для демонстрации несложных типовых алгоритмов.
Алгоритмы сортировки, и их существует несколько, являются типовыми, с ними следует познакомиться, научиться понимать их, а перед собеседованием неплохо будет повторить эти алгоритмы. В реальной практике программирования они вряд ли потребуются, потому что сортировка, как правило, отработана в стандартной библиотеке любого современного языка программирования.

Метки:

javascript, chromium, javascript-client-side, sort, math, array, for, while, random, round