Приветствую тебя дорогой друг! В этом уроке я покажу, как можно реализовать пузырьковую сортировку на 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.
Теперь вы можете взглянуть на программу в деле, а также скачать архив со всеми исходными данными к себе на компьютер.
Посмотреть результат
Скачать
Если у вас есть вопросы по данному уроку, то можете задать их в комментариях – постараюсь ответить.
На этом у меня все, желаю вам удачи, пока!
Если вам нужна помощь в создании какого-либо функционала, сайта, сервиса, тестов или калькуляторов, то готов помочь, подробнее на странице услуг.