Сортировка пузырьком на 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(../image/background.jpg);
	text-align: center;
}

/* блок с шарами - полка */
#nums{
    width: 1000px;
    height: 176px;
    background: url(../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.

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

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

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



Похожие публикации:

Оставить комментарий

Ваш email не будет опубликован. Обязательные поля отмечены *

*

code

Вы можете использовать это HTMLтеги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>