Визуализация алгоритмов сортировки обменом на JavaScript

в 13:49, , рубрики: javascript, Алгоритмы, алгоритмы сортировки, визуализация, визуализация данных

Доброго времени суток всем читателям и авторам habrahabr.ru. Речь в данной статье будет идти о визуализации простейших алгоритмов сортировки.

Визуализация алгоритмов сортировки обменом на JavaScript - 1

На выполнение данной работы меня вдохновил Timo Bingmann – аспирант из Института теоретической информатики и алгоритмов при Технологическом институте Карлсруэ (Германия) [1]. Тимом была написана отличная статья, где можно почитать немного о истории визуализаций и аудификаций алгоритмов [2]. Программисты, как никто знают, как тяжело идет процесс понимания абстрактных сущностей, и как сильно в этом помогают метафоры и методы визуализации. Когда какому-либо объекту из реальной жизни аналогично присваиваются свойства и методы виртуальных объектов.

Выбор алгоритмов

Признаюсь читателю, что программирование на сегодняшний день не является моей профессией. Разумеется, какие-то наработанные навыки у меня уже были. Это BASIC в 2007г. (тогда я постиг ветвление, типы данных, массивы, каверзность оператора GOTO, удобство подпрограмм и впервые написал программу эмулирующую идеальный газ в закрытом сосуде. Если вы не знаете или не помните, в стандартном пакете BASIC, как базовая, была программа визуализации сортировок [3]). Еще из опыта был Pascal в 2012г. В институте, в рамках изучения дискретной математики (писали последовательность Фибоначчи, операции со стеками и базовые сортировки). Исходя из моего опыта было принято решение начать с сортировок обменом как с чего-то знакомого и простого. Ниже я еще немного повествую, с какими сложностями мне пришлось столкнуться при визуализации иных типов сортировок.

Выбор инструментов

Ниже представлены инструменты, используемые для создания визуализации вышеупомянутых алгоритмов.

Язык программирования – JavaScript.

«Довольно необычный выбор!» — скажете вы и будете абсолютны правы. Действительно, на сегодняшний день существует множество языков программирования и библиотеки к ним, которые подходят для поставленной задачи гораздо лучше. Например C++. С применением C++ можно осуществлять управление памятью, а также рисовать графику на экране с использованием значительно меньших ресурсов вычислительной машины. Я не буду сильно углубляться в причины того, что моя жизненная ситуация требует моей быстрейшей переквалификации из исследователя естественных наук в знатока Web tech., в которых JavaScript используется повсеместно, потому что статья в целом получится слишком грустной и даст ненужные поводы для дискуссий в комментариях. Было принято решение совместить приятное с полезным, освежить свои академические знания и слегка подучить вышеупомянутый язык сценариев для web-страниц. И все же, для объективности, мы перечислим положительные и отрицательные стороны выбора:

Плюсы:

  1. Первый и весьма очевидный плюс – доступный всем пользователям интерпретатор. Если для просмотра работы Timo Bingmann нужно скачивать исполняемый файл на машину [4. Раздел Downloads / Open source]. То для исполнения программы на языке JavaScript достаточно установленного браузера в вашем электронном устройстве.
  2. Легко делиться своим творчеством с друзьями (достаточно скинуть им ссылку на демо в соц.сетях)
  3. Легкое оформление UI посредством HTML5 / CSS3. Данная связка быстро и надежно позволяет разместить элементы управления программой.

Минусы:

  1. Первый плюс несет в себе и отрицательные черты – интерпретация и исполнение кода на машине клиента ведет за собой нагрузку на CPU и RAM клиента. Для исполнения программы RAM требуется не так уж и много (около 1,5 мб). Но CPU i5 от Intel машины вашего автора, на самой высокой скорости при тестах был загружен на 35%. Следовательно, мы не исключаем тормозов и подлагиваний на слабых машинах и android-устройствах с малой производительностью.
  2. Поскольку CANVAS использует аппаратное ускорение [5] не исключаем нагрузку и на GPU.

Визуализация и отображение на экране – элемент HTML5: CANVAS.

CANVAS – это холст, на котором можно рисовать объекты посредством команд из js-сценария. У этого метода есть свои минусы, как например плохая масштабируемость при смене масштаба в браузере, в отличии от векторного SVG (который всегда идеален при любых масштабах). Но поскольку в нашем случае вся логика программы находится в js-файле – сложно найти элемент более подходящий для нашей задачи. Так же у CANVAS есть очевидные плюсы, например – масштабирование через CSS, которое автоматически так же масштабирует и систему координат, что позволяет нам осуществлять некоторую адаптивность без потери качества, с помощью media запросов. Уже неплохо! Так же, элемент CANVAS можно сохранить со страницы, нажав по холсту правой кнопкой мыши и выбрав в контекстном меню «сохранить». На этом мы завершим разговор о инструментах и переходим, собственно, к самой программе.

Псевдокод программы:

1. Объявить все глобальные переменные.
2. Подключить CANVAS для визуализации.
3. Подключить Web Audio API. и AudioContext() для аудификации.
4. Получить начальные значения от элементов управления в HTML разметке и записать их в переменные.
5. Исходя из начальных значений генерировать массив элементов и ожидать команд от пользователя.
6. При нажатии кнопки «Reset» стереть холст и посчитать новый массив элементов. Отобразить на экране новый массив.
7. При нажатии кнопки «Play» запустить сортировку по типу, указанному в панели настроек. Изменить вид кнопки на «Pause». При нажатии кнопки «Pause» приостановить сортировку.и изменить вид кнопки на «Play».
8. При изменении значений ползунка Change Speed изменить скорость сортировки.
9. При смене типа сортировки на панели настроек приостановить сортировку, если процесс сортировки инициирован.
10. При смене вида отображения сортировки изменить последовательность отрисовки в CANVAS. Не останавливая процесс сортировки.
11. Если сортировка завершена, сбросить все счетчики, кнопку «Pause» изменить на «Play», пройтись еще раз по массиву зеленым цветом визуально подтверждающим завершение сортировки и ожидать дальнейших действий от пользователя. (По факту в этот момент сортировка уже завершена. Этот пункт сделан чисто из эстетических соображений и со скидкой на человеческое восприятие)

UI
Как уже упоминалось нами выше, для создания UI в браузере мы будем использовать HTML5 и CSS3, нам понадобятся следующие элементы:

  • Заголовок. Nuff said [6]
  • Панель управления.
    Тут будут размещен блок с ползунками настроек и выпадающий список для выбора типа сортировки. Сразу привяжем события к нашим ползункам и списку, чтобы обеспечить вызов необходимых функций в JavaScript-коде:

    HTML

    <!--settings & ranges -->
    <div class="settingsPanel">
    <form>
        <label class="label">Chose sort algorithm type:</label><br>
        <select name = "sortTypeDom" class="softFlowSelect" onchange="changeSortType()">
            <option value = "combSort">Comb sort</option>
            <option value = "bubbleSort">Bubble sort</option>
            <option value = "cocktailSort">Cocktail sort</option>
        </select>
    </form><br>
        <label class="label">Settings:</label><hr>
        <div class="settingsRange">
            Sphere Radius & Lines height / Brightness<br>
            <input title="Sphere Radius" class="rangeCSS" type="range" min="30" max="150" step="1" value="75" oninput="changeRadius()" id="sphereRadius"><br>
            Number of elements<br>
            <input title="Number of elements" class="rangeCSS" type="range" min="30" max="240" step="1" value="125" oninput="calcNewArray()" id="elementsNumb"><br>
            Speed<br>
            <input title="Speed" class="rangeCSS" type="range" min="10" max="200" step="5" value="105" oninput="changeSpeed()" id="codeSpeed"><br>
            Volume<br>
            <input title="Volume" class="rangeCSS" type="range" min="0" max="0.05" step="0.0005" value="0.025" id="volume">
        </div>
    </div>

  • Кнопки старта, сброса и вида отображения.

    Мы будем использовать три вида отображения сортировки на нашем холсте, помимо смещения порядка столбиков по длине (что уже стало классикой) это будет градиент от темного к светлому по степени интенсивности и окружность со смещением порядка столбиков по длине. Это будет небольшой новый вклад в визуализацию сортировок. Очевидно нам понадобятся кнопки, чтобы изменять тип отображения, и нам понадобятся кнопки управления «Play» и «Reset». Большинство классов в нижестоящем коде используются просто для оформления:

    HTML

    <div class="sortButton transition" id = "roundView" onclick="changeSortView('roundView')">
    </div>
    <div class="sortButton transition" id = "classicView" onclick="changeSortView('classicView')">
    </div>
    <div class="sortButton transition" id = "gradientView" onclick="changeSortView('gradientView')">
    </div><br>
    <div class="buttonContainer">
        <div class="playButton button transition" id = "firstButton" onmousedown="mouseDown()" onclick="startButton()">
            <div class="sprite-play"></div>
        </div>
        <div class="resetButton button transition" onclick="calcNewArray()">
            <div class="sprite-reset"></div>
        </div>
    </div><br>

    Transition это уникальное свойство добавленное в CSS3 позволяющее осуществлять плавное изменение между двумя состояниями элемента. Я не буду описывать очевидное оформление в этой статье, поскольку это не представляет никакого интереса, уделив внимание только transition. Класс transition выглядит так:

    .transition {
            transition: 0.4s;
            }

    Ну и из интересного, это конечно масштабирование холста CANVAS в CSS3. Как уже упоминалось выше – вместе с элементом масштабируется система координат, что позволяет нам создавать какие угодно большие или малые отображения холста без всяких проблем с качеством и координатами. Например, порадуем владельцев HD мониторов:

    @media screen and (max-width: 2000px) {
            canvas {
            width: 1000px;
            height: 1000px;
            }
            ... }

    Для мобайла был установлен размер холста в 800px.

  • Собственно, сам холст.
    <div class="sortPlace">
            <canvas id="canvas" width="900" height="900"></canvas>
        </div>

  • Подвал. Nuff Said

JavaScript-код

Сразу расстрою многих читателей. Я знаю, что на Хабрахабре любят ООП. Однако, программа была написана в процедурном стиле, поскольку на момент написания визуализации мой опыт был ограничен самостоятельным ковырянием в BASIC и решении некоторых задач по дискретной математике на Pascal. Более десяти лет назад я активно использовал подпрограммы в BASIC, и вот две недели назад изучив функции в JavaScript почувствовал ностальгию. Ведь основные задачи у подпрограмм и функций очень похожие, а именно сократить количество кода в программе обернув повторяющийся код в функцию/подпрограмму. Я не помню можно ли было отправлять в подпрограмму аргументы, если вы помните, то обязательно напишите это в комментариях под статьей. С ООП стилем я познакомился уже после того, как написал половину кода для визуализации. Мне очень понравится этот подход. ООП это определенно хорошо, но переписывать код я пожалуй не буду (к тому же ООП в JavaScript имеет свою специфику, кто знает – тот поймет).

Начнем мы по классике с блок-схемы, чтобы иметь общее представление о архитектуре программы:

Если Хабрахабр не умеет в масштабирование по клику — вот ссылка на вектор и растр.

Визуализация алгоритмов сортировки обменом на JavaScript - 2

Я не буду копировать сюда весь код из программы. Если кому-либо станет действительно интересно загляните в репозиторий на GitHub и ужасайтесь уже там. Пойдем с вами прямо по псевдокоду:

Очень большой блок текста с JavaScript кодом и пояснениями:

1. Объявить все глобальные переменные.
Ну тут все довольно просто. Программа содержит множество функций, зачастую использующих одинаковые переменные. Особенность JavaScript в том, что переменная объявленная внутри функции доступна только, собственно, внутри функции [7]. В то время, как переменная объявленная в глобальном пространстве видна везде. Это первая сложность, с которой я столкнулся. Пришлось немного почитать. Разумеется, по возможности мы будем объявлять переменные внутри функций. Итак, глобальными у нас будут переменные отвечающие за:
Процесс сортировки (сортировка в процессе/сортировка остановлена):

// sort state
        var playing = false;

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

//sphere radius global vars for RoundView
        var radiusValue =  +document.getElementById("sphereRadius").value,
        diffRadiusValue = 0;

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

var colors = ["#839192", "#80ffbf", "#566573", "#ff8080", "#00cc00", "#006600", "#c2d6d6"],
        colorPick = 3;

2. Подключить CANVAS для холста и соединить его с HTML разметкой.
3. Подключить Audio API. AudioContext() для аудификации.

Эти два пункта псевдокода мы объединим, т.к. эти переменные можно логично объявить одним блоком. И в этом блоке сразу задаем значение переменной canvasSize (которая задействована при генерации длины элементов массива, нахождении координат середины холста, отрисовки окружности с отображением с окружностью) и мы сразу привязываем контроль громкости к нашему ползунку громкости из разметки:

//canvas pics & audio prep.
        var audio = new AudioContext(),
        volControl = document.getElementById("volume"),
        canvas = document.getElementById("canvas"),
        ctx = canvas.getContext("2d"),
        canvasSize = 900;

Далее в коде объявляем пустой массив и вспомогательные глобальные переменные. Которые устанавливают стартовые настройки и используются в функциях сортировок, например, переменная отвечающая за направление движения для шейкерной сортировки, счетчики которые отслеживают завершенность массива и отвечают за завершение сортировки, шаг для сортировки расческой и пр. за все это в псевдокоде отвечает пункт 4. Задать начальные значения для элементов управления в HTML разметке.

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

calcNewArray();

Весь оставшийся код в файле .js представляет из себя декларирование функций, рассмотрим некоторые из них по мере необходимости, некоторые очевидные получат просто описание. Если вам интересно вы всегда можете посмотреть их в репозитории.
Итак, функция calcNewArray собирающая новый массив, берет значение количества элементов из ползунка в HTML разметке, значение размера холста и радиуса окружности для соответствующего вида вычитается из максимального размера элементов (чтобы при изменении радиуса элементы не выходили за пределы холста). Унарный "+" перед значениями получаемые от ползунков в разметке ставится обязательно, чтобы произвести преобразование типа данных «String» -> «Number». Первый цикл for заполняет наш массив элементами с максимально допустимой длиной (по холсту), второй цикл равномерно распределяет длину элементов. В завершении функции сбрасываются все дополнительные параметры для сортировок и вызываются функции которые перемешивают массив и обновляют холст:

function calcNewArray() {
    array=[];
    for (var i = 0; i < +document.getElementById("elementsNumb").value; i++) {
        array.push(Math.round(( (canvasSize/2) - (+document.getElementById("sphereRadius").value) - 60)));
    }
    for (i = 0; i < array.length; i++) {
        array[i] =  array[i] * ((i)*((0.64/array.length))) + 90;
    }
    step = array.length-2;
    time = 0;
    direction = true;
    compareRandom(array);
    resetImage();
}
        }

Изначально я просто заполнял массив случайными элементами в промежутке от 50 до длины холста с вычетом радиуса, однако случайная генерация не дает такой ровный и красивый массив!

Далее опишем функцию startOsc отвечающую за звук при проверке элементов. Функция принимает на вход параметр частоты и представляет из себя осциллятор, последовательно подключенный к гейну. Чтобы звук сильно не резал слух при обрыве осциллятора, мы указываем время нарастания (атаки) звуковой волны и затухания.
image
Кто хоть раз подключал электрогитару – тот примерно поймет принцип работы WebAudioApi, те, кто не подключал, может прочитать об этом примерно тут [8] и более простым языком здесь [9] и для маньяков, которые хотят писать музыку есть фундаментальная книга «Web audio api» издательства O'Reilly:

function startOsc(freq) {
    var attack = 25,
        decay = 60,
        gain = audio.createGain(),
        osc = audio.createOscillator();
    gain.connect(audio.destination);
    gain.gain.setValueAtTime(0, audio.currentTime);
    gain.gain.linearRampToValueAtTime(volControl.value, audio.currentTime + attack / 700);
    gain.gain.linearRampToValueAtTime(0, audio.currentTime + decay / 700);
    osc.frequency.value = (freq+100)*1.4;
    osc.type = "square";
    osc.connect(gain);
    osc.start(0);

    setTimeout(function() {
        osc.stop(0);
        osc.disconnect(gain);
        gain.disconnect(audio.destination);
    }, decay);
}

Далее по псевдокоду: 6. При нажатии кнопки «Reset» стереть холст, посчитать новый массив элементов
Здесь все довольно просто, в HTML разметке внутри блока нами указывается вызов функции при обработке события onclick:

<div class="resetButton button transition" onclick="resetButton()">

Сама функция resetButton() вызывает уже описанную выше calcNewArray(), и resetImage(), resetImage() представляет из себя функцию, которая отвечает за очистку холста и вызов функции drawArray, получающей массив на входе и выполняющей задачу рисования массива на холсте:

function resetImage () {
    ctx.clearRect(10, 10, canvasSize-20, canvasSize-20);
    if (sortView == "roundView") {
        drawCircle(+document.getElementById("sphereRadius").value, colors[6]);
    }
    drawArray(array);
}

drawArray(array) это функция с ветвлением по количеству доступных типов сортировок (в нашем случае пузырьком, расческой и шейкерной), c вложенными циклами, которая подготавливает аргументы для функции lineFunction(pommel, radCord, color, radius). После того, как из кода, отвечающего за непосредственно логику сортировки, вызывается функция drawArray(array), в зависимости от типа сортировки обрабатывается цикл подготовки аргументов для функции lineFunction. Далее по количеству элементов в массиве вызывается lineFunction с аргументами: pommel — булевая (наличие или отсутствие «наконечника» у элемента), radCord — порядковый номер массива, color — цвет, и radius — текущий радиус окружности (используется только для вида с окружностью). Внутри lineFunction аналогично осуществляется ветвление, но по видам отображения (в нашем случае вид с окружностью, классический вид, и градиент). Обе функции функции: drawArray и lineFunction содержат достаточно большой объем кода. Для демонстрации я покажу вам код с ветвлением на сортировку пузырьком, и классический вид:

function drawArray(array) {
    ctx.lineWidth = 2*Math.PI*(+document.getElementById("sphereRadius").value)/array.length;
...
    if (sortType === "bubbleSort") {
        for (var i = 0; i < array.length; i++) {
            lineFunction(false, i, colors[0], +document.getElementById("sphereRadius").value);
            lineFunction(false, time-1, colors[colorPick], +document.getElementById("sphereRadius").value);
            lineFunction(false, time, colors[colorPick], +document.getElementById("sphereRadius").value);
            lineFunction(true, i, colors[2], +document.getElementById("sphereRadius").value);
        }
    }
...
   
}
function lineFunction(pommel, radCord, color, radius) {
...
    if (sortView == "classicView") {
        ctx.strokeStyle = color;
        ctx.lineWidth = canvasSize*0.75 / array.length;
        if (pommel) {
            ctx.beginPath();
            ctx.moveTo(radCord * (canvasSize*0.9 / array.length)+30, canvasSize/2 - array[radCord]);
            ctx.lineTo(radCord * (canvasSize*0.9 / array.length)+30, canvasSize/2 - array[radCord] - canvasSize*0.8 / array.length);
            ctx.stroke();
        } else {
            ctx.beginPath();
            ctx.moveTo(radCord * (canvasSize*0.9 / array.length)+30, canvasSize/2);
            ctx.lineTo(radCord * (canvasSize*0.9 / array.length)+30, canvasSize/2 - array[radCord]);
            ctx.stroke();
        }
    }
...

Обратите внимание, что функция drawArray отправляет два элемента с цветом colors[colorPick], в lineFunction для отрисовки. Значение colorPick – глобальное и присваивается каждый раз в коде, который отвечает непосредственно за логику сортировки. Это или светло-зеленый цвет если элементы не меняются местами или светло-красный если элементы поменялись. Рисование на холсте происходит следующим образом: сначала подается команда ctx.beginPath(); что означает «начало пути» потом указываются команды moveTo и lineTo с аргументами в виде декартовых координат. Чтобы вам было более понятно, я проведу аналогию: представьте, что у вас в руках карандаш. Команда moveTo – «передвинуть», означает, что вы просто двигаете над холстом карандаш в указанную точку. Команда lineTo – «прочертить», означает, что вы проводите карандашом по холсту создавая таким образом путь. В завершение, команда stroke(); говорит вам возьми кисть размера lineWidth и макни ее в краску strokeStyle, (мы же уже заранее сказали, какую краску и кисть подготовить) и обведи свою линию начерченную карандашом. В Adobe: Photoshop есть похожий инструмент – Path, с помощью которого можно создавать и редактировать пути. Там же существует в контекстном меню опция Stroke Path, которая позволяет провести выбранным инструментом по пути. Пользователям с опытом в фотошопе такая аналогия будет более ясна. Подробнее про CANVAS и метод Stroke вы можете почитать в статье на нашем сайте «CANVAS шаг за шагом: Основы» [10] ну и более упорядоченно и подробно здесь [11]

7. При нажатии кнопки «Play» запустить сортировку по выбранному типу на панели настроек. Изменить вид кнопки на «Pause». При нажатии кнопки «Pause» приостановить сортировку
По аналогии с кнопкой «Reset» вызываем функцию, которая в ситуации, если процесс сортировки остановлен, запустит процесс при инициализировав функцию initSort() и сменит спрайт на иконку паузы и цвет кнопки. Если сортировка находится в процессе, нажатие кнопки приостановит ее:

function startButton() {
    if (!playing) {
        playing = true;
        document.getElementsByClassName("sprite-play")[0].style.backgroundPosition = "-60px -5px";
        document.getElementById("firstButton").style.background = "linear-gradient(hsla(0, 64%, 87%, 1), hsla(0, 64%, 57%, 1))";
        initSort();
    } else {
        playing = false;
        document.getElementsByClassName("sprite-play")[0].style.backgroundPosition = "-60px -45px";
        document.getElementById("firstButton").style.background = "linear-gradient(hsla(136, 64%, 87%, 1), hsla(136, 64%, 57%, 1))";
        clearInterval(drawing);
        resetImage();
    }
}

8. При изменении ползунка «Change Speed» изменить скорость сортировки.
Очень просто, на ползунок в HTML коде вешаем событие oninput которое вызывает функцию:

function changeSpeed() {
    if (playing) {
        clearInterval(drawing);
        initSort();
    }
}

Если сортировка в процессе, то эта функция сбросит интервал и инициирует новый. Т.к. функция initSort(); берет скорость из текущего значения элемента на нашей странице, при остановленной сортировке действий не требуется.

9. При смене вида отображения сортировки изменить вид отображения в CANVAS коде.
Обрабатываем событие onclick уже по нашим дивам с картинками видов, заодно закрашиваем фон выбранному блоку c использованием HSLA:

function changeSortView(view) {
    document.getElementById("roundView").style.backgroundColor="";
    document.getElementById("classicView").style.backgroundColor="";
    document.getElementById("gradientView").style.backgroundColor="";

    sortView = view;
    if (sortView == "roundView") {
        document.getElementById("roundView").style.backgroundColor = "hsla(163, 81%, 80%, 1)";
    }
    if (sortView == "classicView") {
        document.getElementById("classicView").style.backgroundColor = "hsla(163, 81%, 80%, 1)";
    }
    if (sortView == "gradientView") {
        document.getElementById("gradientView").style.backgroundColor = "hsla(163, 81%, 80%, 1)";
    }
    resetImage();
}

строковая переменная sortView так же используется в lineFunction при ветвлении и, таким образом, мы получаем на экран именно то — что нам нужно.

10. Если сортировка завершена, сбросить все счетчики, кнопку «Pause» пройтись еще раз по массиву с зеленым цветом. И ожидать дальнейших действий от пользователя.
Идея полностью позаимствована у Тимо Бингмана. Ну да ладно, думаю, он на нас не обидится и по русски вряд ли читать умеет. Однако, суть нижеописанной функции не только в визуальном сопровождении, но и в том, что сортировку необходимо еще грамотно завершить, интервалы обнулить, а некоторые переменные сбросить. Если этого не сделать — то рождаются баги при повторных запусках. Итак, в момент завершения сортировки, из кода, который отвечает за непосредственно сортировку, вызывается функция:

function terminateProgram() {
    clearInterval(drawing);
    ctx.clearRect(10, 10, canvasSize-20, canvasSize-20);
    time = 0;
    colorPick = 3;
    ctx.lineWidth = 2 * Math.PI * (+document.getElementById("sphereRadius").value) / array.length;
    for (var i = 0; i < array.length; i++) {
        lineFunction(false, i, colors[0], +document.getElementById("sphereRadius").value);
        lineFunction(true, i, colors[2], +document.getElementById("sphereRadius").value);
        if (sortView == "roundView") {
            drawCircle(+document.getElementById("sphereRadius").value, colors[6]);
        }
    }
    i = 0;
    var finishDrawing = setInterval(function() { // Last green-style check 
        if (i < array.length) {
            startOsc(array[i]);
            lineFunction(false, i, colors[1], +document.getElementById("sphereRadius").value);
            lineFunction(true, i, colors[5], +document.getElementById("sphereRadius").value);
            if (sortView == "roundView") {
                drawCircle(+document.getElementById("sphereRadius").value);
            }
        } else {
            if (sortView == "roundView") {
                drawCircle(+document.getElementById("sphereRadius").value, "#b3ffcc");
            }
            clearInterval(finishDrawing);
            arrayLevel = 0;
            arrayLevelLow = 0;
            playing = false;
            document.getElementsByClassName("sprite-play")[0].style.backgroundPosition = "-60px -45px";
            document.getElementById("firstButton").style.background = "linear-gradient(hsla(136, 64%, 87%, 1), hsla(136, 64%, 57%, 1))";
            console.log("Array with " + array.length + " elements was completely sorted via " + sortType + " technique!" );

            // Program shutdown!
        }
        i++;
    }, Math.abs(+document.getElementById("codeSpeed").value-200)*0.7);
}

Таким образом, кнопки сброшены, переменные сброшены и наша программа готова к повторному запуску.

До сюда дойдут единицы и эту часть текста все равно никто не прочитает, поэтому я признаюсь в том, что я люблю читать статьи на Хабре во время рабочего дня с рабочего компьютера. Мой любознательный читатель, если тебе интересны сами алгоритмы сортировки и их реализация, есть много замечательных книг на эту тему но самая очевидная и всем известная The Art of Computer Programming (TAOCP) [12], если тебе интересно как выглядит мой код на JavaScript

я помещу его под кат сюда:

function sort() {
    ctx.clearRect(10, 10, canvasSize-20, canvasSize-20);

    // **************// comb sort code & conditions //************************************************//

    if (sortType === "combSort") {
        if (array[time] > array[time+step]) {
            colorPick = 3;
        } else {
            colorPick = 1;
        }
        drawArray(array);
        if (sortView == "roundView") {
            drawCircle(+document.getElementById("sphereRadius").value, colors[6]);
        }
        if (time + step >= array.length) {
            time = 0;
            step = (step == 1) ? step : Math.floor(step / 1.25);
        }
        if (arrayLevel > array.length) {
            terminateProgram();
        }
        for (var i = 0; i < array.length-1; i++) {
            if (array[i] <= array[i+step]) {
                arrayLevel++;
            } else {
                arrayLevel=0;
            }
        }
        if (time < array.length-1-arrayLevel) {
            startOsc(array[time+step]);
            startOsc(array[time]);

            if (array[time] > array[time+step]) {
                var temp = array[time];
                array[time] = array[time+step];
                array[time+step] = temp;
            }
            time++;
        } else {
            time = 0;}
    }
    // *******// stupid-style bubble sort & conditions //*************//

    if (sortType === "bubbleSort") {

        ctx.clearRect(10, 10, canvasSize-20, canvasSize-20);

        if (array[time] > array[time+1]) {
            colorPick = 3;
        } else colorPick = 1;

        drawArray(array);
        if (sortView == "roundView") {
            drawCircle(+document.getElementById("sphereRadius").value, colors[6]);
        }

        if (arrayLevel > array.length) {
            terminateProgram();
        }

        for (var i = 0; i < array.length-1; i++) {
            if (array[i] <= array[i+1]) {
                arrayLevel++;
            } else {
                arrayLevel=0;
            }
        }

        if (time < array.length-1-arrayLevel) {

            startOsc(array[time]);
            startOsc(array[time+1]);

            if (array[time] > array [time+1]) {
                var temp = array[time+1];
                array[time+1] = array[time];
                array[time] = temp;
            }
            time++;

        } else {
            time = 0;}
    }
    // ********************// cocktail shaker sort //*********************************//

    if (sortType === "cocktailSort") { //
        if (arrayLevel+arrayLevelLow > array.length) {
            terminateProgram();
        }

        ctx.clearRect(10, 10, canvasSize-20, canvasSize-20);
        drawArray(array);
        if (sortView == "roundView") {
            drawCircle(+document.getElementById("sphereRadius").value, colors[6]);
        }

        if (direction) {
            for (var i = 0; i < array.length-1; i++) {
                if (array[i] < array[i+1]) {
                    arrayLevel++;
                } else {
                    arrayLevel=0;
                }
            }
        } else {
            for (i = array.length; i > 1; i--) {
                if (array[i] > array[i-1]) {
                    arrayLevelLow++;
                } else {
                    arrayLevelLow=0;
                }
            }
        }

        if (direction) {
            if (time < array.length-arrayLevel-1) {
                startOsc(array[time]);
                startOsc(array[time+1]);
                if (array[time] > array [time+1]) {
                    var temp = array[time+1];
                    array[time+1] = array[time];
                    array[time] = temp;
                    colorPick = 3;
                } else {
                    colorPick = 1;
                }
                time++;

            } else {
                direction=false;
            }
        }


        if (!direction) {
            if (time > arrayLevelLow) {
                startOsc(array[time]);
                startOsc(array[time-1]);
                if (array[time] > array [time+1]) {
                    var temp = array[time+1];
                    array[time+1] = array[time];
                    array[time] = temp;
                    colorPick = 3;
                } else {
                    colorPick = 1;
                }
                time--;

            } else {
                direction=true;
            }
        }
    }
}
        }

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

Заключение

В целях изучения HTML5, CSS3, JavaScript, элемента CANVAS, WebAudio API, нами была разработана страница, которая визуализирует простейшие алгоритмы сортировки обменом. Такие сортировки, как расческа, шейкерная сортировка и сортировка пузырьком. Во время разработки у автора возникло много вопросов, т.к. автор еще неопытен. Количество строк многострадального кода ≈500. Количество затраченного времени ≈2 недели в неспешном темпе. Количество полученного удовольствия от достигнутого результата – не исчисляется цифрами. Спасибо Вам, что прочитали мою первую статью.


Ссылка на демо (бесплатный хостинг на bitbucket, не уверен в корректной работе при большом количестве посетителей.

Ссылка на YouTube плейлист с демонстрацией визуализации

Ссылки на используемую литературу и источники указанные в статье

Репозиторий с кодом из статьи на моем GitHub | Блок-схема в растровом изображении

[1] GitHub Timo Bingmann
[2] Институт теоретической информатики и алгоритмов при Технологическом институте Карлсруэ
[3] Ссылка на видео демонстрации программы визуализации сортировок, которая входила в стандартный пакет BASIC
[4] Статья Timo Bingmann о визуализации алгоритмов, можно скачивать уже скомпилированый исполняемый файл на машину в разделе Downloads / Open source
[5] Статья на ixbt о аппаратном ускорении в браузерах, в частности о CANVAS / Игорь Дериев – 2011
[6] Тут мне нечего добавить
[7] Хорошая статья на Хабрахабр о области видимости переменных в JavaScript и не только / Алексей – 2011
[8] Спецификация Web Audio API на сайте фаерфокса
[9] Начальное руководство и первые шаги в Web Audio API / Boris Smus – последнее обновление 2013
[10] Хорошая статья на Хабрахабре «CANVAS шаг за шагом: Основы» / Alexander Shpak – 2011
[11] Подробная, качественная и годная спецификация по CANVAS от w3s
[12] Фундаментальная серия томов по алгоритмам «The Art of Computer Programming (TAOCP)» / Donald Knuth – выпускается с 1968

Автор: ArVaganov

Источник

Поделиться

* - обязательные к заполнению поля