[Из песочницы] Визуализация алгоритмов сортировки обменом на JavaScript26.02.2017 18:34

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

// sort state
        var playing = false;

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

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;

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

calcNewArray();

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();
}
        }

Далее опишем функцию startOsc отвечающую за звук при проверке элементов. Функция принимает на вход параметр частоты и представляет из себя осциллятор, последовательно подключенный к гейну. Чтобы звук сильно не резал слух при обрыве осциллятора, мы указываем время нарастания (атаки) звуковой волны и затухания.

Кто хоть раз подключал электрогитару — тот примерно поймет принцип работы 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:

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();
        }
    }
...

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();
    }
}

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();
}

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;
            }
        }
    }
}
        }