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


Раздел: Программирование

Дата последнего изменения: 2017-04-23 22:56:28

Просмотров: 14107

Читайте также:

Игра Угадай число на JavaScript!
Html таблица на JavaScript
Движущаяся машина на JavaScript!
Видео галерея на JavaScript!
Падающий мяч на JavaScript!
Генератор случайных картинок на JavaScript!
Как изменить фон страницы на JavaScript
Анимация на чистом javascript

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

* Комментарий: (отменить ответ)

* Ваше имя:

Ваш e-mail:

*