Сортировка пузырьком на JavaScript

Приветствую тебя дорогой друг! В этом уроке я покажу, как можно реализовать пузырьковую сортировку на JavaScript!

Сортировка пузырьком на JavaScript

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

Сначала немного теории: если говорить простым языком, то суть пузырьковой сортировки заключается в том, что мы поочередно берем пару чисел (текущее и предыдущее) и сравниваем их. Если текущее число меньше предыдущего, то меняем их местами.

Теперь давайте рассмотрим конкретный пример, допустим у нас есть вот такой вот набор чисел:

4, 3, 7, 1, 9

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

Сначала мы берем первую пару чисел (4 и 3) и сравниваем, если 3 < 4, то меняем 3  и 4 местами, то есть  4 встанет на вторую позицию и ряд будет выглядеть так:

3, 4, 7, 1, 9

Дальше мы берем следующую пару чисел (теперь уже 4 и 7), так как 7 больше 4, то менять ничего не нужно, переходим к следующей паре (7 и 1). 1 меньше 9, значит меняем числа местами и ряд станет таким:

3, 4, 1, 7, 9

и так далее – все шаги:

  • 3, 1, 4, 7, 9 – поменяли 1 и 4
  • 1, 3, 4, 7, 9- поменяли 1 и 3

Все, числа отсортированы!

 

На JavaScript алгоритм будет выглядеть так:

var num_array = [4, 3, 7, 1, 9];

for (i = 1; i < 10; i++) {

        for (j = 1; j < 10; j++) {

                if( num_array[j] < num_array[j-1] ){
                        var change_obj = num_array[i];
                        num_array[i] = num_array[i-1];
                        num_array[i-1] = change_obj;
                }
        }
}

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

Будут генерироваться 10 чисел в диапазоне от -9999 до 9999, оформленных как шары (или пузыри, не знаю на что больше похоже):

Пузыри

Также, эти шары будут лежать как бы на полке, для этого возьмем такую картинку:

Полка

 

Ну и основой всего интерфейса будет фоновое изображение стены с диваном:

Фон - стена с диваном

Над диваном будет висеть полка с числами (шарами), а под диваном будет выводиться информация о ходе сортировки.

 

Требования

Итак, программа должна отвечать следующим требованиям:

  • оформить числа в виде пузырьков;
  • должна быть анимация обмена чисел;
  • числа должны обмениваться с задержкой в 1 секунду;
  • возможность генерировать случайные числа;
  • перед тем, как начнется сортировка, должна пропасть полка;
  • во время сортировки должна блокироваться кнопки – “Отсортировать числа”;
  • должна выводиться информация о номере текущего прохода.

 

Реализация

Верстка очень простая, можно выделить следующие элементы:

  • 2 кнопки;
  • фоновое изображение;
  • изображение полки;
  • 2 строчки текста о том, как пользоваться программой;
  • блок с информацией о ходе сортировки.

 

HTML верстка:

        <div id="wrap"><!-- ОБЩИЙ БЛОК - ОБЕРТКА -->
                <p class="button randomGenerate">Сгенерировать числа</p>
                <button class="button sorting" disabled>Отсортировать числа</button>
                <div id="instructions"><!-- ИНСТРУКЦИЯ -->
                        <p>Для генерации случайных чисел нажмите на кнопку - "Сгенерировать числа".</p>
                        <p>Для сортировки сгенерированных чисел нажмите на кнопку - "Отсортировать числа".</p>
                </div><!-- /ИНСТРУКЦИЯ -->
                <div id="nums"></div>
                <div id="info"><!-- ИНФОРМАЦИЯ О СОСТОЯНИИ СОРТИРОВКИ -->
                        <span class="result"></span><br>
                        <span class="cur_step"></span><br>
                        Исходные числа: <span class="original_numbers"></span>
                </div><!-- /ИНФОРМАЦИЯ О СОСТОЯНИИ СОРТИРОВКИ -->
        </div><!-- /ОБЩИЙ БЛОК - ОБЕРТКА -->

 

CSS стили:

body{
        font-family:verdana;
        color:#444;
        padding: 0;
        margin: 0;
        background: #636363;
}

/* стили для кнопок */
.button{
    text-decoration: none;
    font-size: 20px;
    margin-right: 20px;
    color: #fff;
    background: #636363;
    padding: 4px 8px;
    border: 0;
    cursor: pointer;
    width: 300px;
    display: inline-block;
}
.button:disabled,.button[disabled]{
    opacity: 0.3;
        cursor: no-drop;
}
#wrap{
    width: 1600px;
        height: 900px;
    margin: 0 auto;
        background: url(/wp-content/uploads/../image/background.jpg);
        text-align: center;
}

/* блок с шарами - полка */
#nums{
    width: 1000px;
    height: 176px;
    background: url(/wp-content/uploads/../image/shelf.jpg);
    margin: 0 auto;
}

/* стили для шара-числа */
#nums .num{
        width: 80px;
        height:80px;
        display: inline-block;
        cursor: default;
    color: #fff;
    margin: 68px 6px 0 6px;

        background: -moz-linear-gradient(top,  #7abcff 0%, #60abf8 44%, #4096ee 100%); /* FF3.6-15 */
        background: -webkit-linear-gradient(top,  #7abcff 0%,#60abf8 44%,#4096ee 100%); /* Chrome10-25,Safari5.1-6 */
        background: linear-gradient(to bottom,  #7abcff 0%,#60abf8 44%,#4096ee 100%); /* W3C, IE10+, FF16+, Chrome26+, Opera12+, Safari7+ */
        filter: progid:DXImageTransform.Microsoft.gradient( startColorstr='#7abcff', endColorstr='#4096ee',GradientType=0 ); /* IE6-9 */

        -webkit-border-radius: 50%;
        -moz-border-radius: 50%;
        border-radius: 50%;
        text-align:center;
        vertical-align:middle;
        line-height: 80px;
        box-shadow: inset -10px -10px 90px #000,
                          10px 10px 20px black,
                          inset 0px 0px 10px black;
}

/* стили для текста-инструкции */
#instructions{
        font-size: 18px;
    font-weight: bold;
}

/* блок, в котором выводится информация о состоянии сортировки */
#info{
    width: 850px;
    border: 3px solid #636363;
    margin: 420px 362px 0 362px;
    padding: 10px;
    text-align: left;
    background: #fff;
    font-size: 20px;
        cursor: default;
        -webkit-border-radius: 10%;
        -moz-border-radius: 10%;
        border-radius: 10%;
}

 

Реализация сортировки на JavaScript (JQuery):

$(document).ready(function(){
        var minNum,maxNum,random_num,i,change_obj,num1,num2,step,obj1,obj2,intervalID,timeoutID; //инициализация переменных
        var num_array = new Array(); //массив для чисел, которые будут отсортированы

        //Генерация случайных чисел
        $('.randomGenerate').click(function(){
                $('.sorting').removeAttr('disabled').show(); //делаем кнопку "Отсортировать числа" активной
                $('#nums,#info span').html(''); //стираем сгенерированные числа и данные о состоянии сортировки
                $('#nums').css('backgroundImage', 'url(image/shelf.jpg)'); //задаем фон (полка) для блока с числами (шарами)

                clearTimeout(timeoutID); //отмена выполнения таймера
                clearInterval(intervalID); //отмена выполнения интервала

                //Генерация случайных чисел и заполнение исходной строки с числами, массива и блока с "Шарами" на полке
                for (i = 0; i < 10; i++) {
                        minNum = -9999; //минимальное число
                        maxNum = 9999;  //максимальное число
                        randomNum = Math.round((Math.random() * (maxNum - minNum) + minNum)); //случайное число от минимального до максимального
                        $('#info .original_numbers').append(randomNum + ' '); //заполнение блока с исходными данными случайными числами
                        num_array[i] = randomNum; //заполнение массива случайными числами
                        $('#nums').append('<div class="num">' + randomNum + '</div>'); //генерация "шаров" с числами
                }
        });

        //Сортировка чисел
        $('.sorting').click(function(){
                $('#nums').css('backgroundImage', 'none'); //убираем фон под шарами-числами (полка)
                $('#info .cur_step').show(); //делаем видимым информацию о номере текущего прохода
                $(this).attr('disabled','disabled'); //делаем кнопку "Отсортировать числа" неактивной
                step = 1; //задаем начальное значение для внешнего цикла (количество проходов)

                //функция сортировки
                function sorting() {

                        //проверяем количество выполненных проходов (шагов), чтобы остановить сортировку, когда выполнено 10 проходов
                        if( step < 11 ){
                                $('#info .cur_step').text('Текущий проход: ' + step + '/10'); //выводим номер текущего прохода
                                step++; //увеличиваем значение проходов
                                i = 1; //задаем начальное значение для внутреннего цикла (для проходов по каждому из чисел)
                                $('#info .result').text('Идет сортировка..'); //выводим информацию о том, что в данный момент числа сортируются

                                //функция, которая будет выполняться с задержкой в 1 секунду
                                (function() {
                                        if (i < 10) { //проверяем значение внутреннего цикла, чтобы обойти 10 пар чисел
                                                if( num_array[i] < num_array[i-1] ){ //сравниваем текущее и предыдущее число массива
                                                        num1 = i; //сохраняем индекс текущего элемента массива
                                                        num2 = i-1; //сохраняем индекс предыдущего элемента массива
                                                        obj1 = $('#nums .num:eq('+num1+')'); //производим выборку текущего числа(шара)
                                                        obj2 = $('#nums .num:eq('+num2+')'); //производим выборку предыдущего числа(шара)
                                                        obj1.swap(obj2); //меняем (визуально) текущий шар (obj1) с предыдущим (obj2)

                                                        //обмениваем числа в массиве
                                                        change_obj = num_array[i];
                                                        num_array[i] = num_array[i-1];
                                                        num_array[i-1] = change_obj;

                                                        timeoutID = setTimeout(arguments.callee, 1000); //выполняем функцию, которая выполняется в данный момент, задав таймер на 1 секунду, для задержки соответственно на 1 секунду
                                                }else{
                                                        timeoutID = setTimeout(arguments.callee, 0); //выполняем функцию, которая выполняется в данный момент, задав таймер на 0, чтобы не было задержки, когда числа не нужно обменивать
                                                }
                                                i++;
                                        }else{ //если на текущем проходе было проверено 10 пар чисел, то отменяем выполнение интервала, чтобы не было задержки между проходами
                                                clearInterval(intervalID); //отмена выполнения интервала
                                                sorting();  //запускаем функцию сортировки
                                                intervalID = setInterval(sorting, 10000); //запускаем выполнение функции sorting с интервалом в 10 секунду
                                        }
                                })();
                        }else{
                                clearTimeout(timeoutID); //отмена выполнения таймера
                                clearInterval(intervalID); //отмена выполнения интервала
                                $('#info .result').text('Сортировка окончена!'); //оповещаем пользователя о том, что сортировка окончена
                                $('#info .cur_step').hide(); //скрываем информацию о номере текущего прохода
                        }
                }
                sorting(); //запускаем функцию сортировки
        });
});

Как видно из кода, я дал комментарий практически по каждой строке, если говорить вкратце, то можно выделить следующие операции:

  • объявление переменных и массива;
  • выполнение функции генерации случайных чисел;
  • функция сортировки.

В отдельном файле имеется скрипт обмена двух элементов, то есть анимация обмена, ее я нашел в открытом доступе на Github.

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

Посмотреть результат

Скачать

Если у вас есть вопросы по данному уроку, то можете задать их в комментариях – постараюсь ответить.

На этом у меня все, желаю вам удачи, пока!

Если вам нужна помощь в создании какого-либо функционала, сайта, сервиса, тестов или калькуляторов, то готов помочь, подробнее на странице услуг.