Skip to content

Latest commit

 

History

History
146 lines (113 loc) · 12.5 KB

bubble-sort.md

File metadata and controls

146 lines (113 loc) · 12.5 KB
Raw

Пузырьковая сортировка

Итак попробуем начать рассмотрение алгоритмов сортировки начиная с самой простой сортировки - пузырьковой.

Для тех кто в танке

Для тех кто совсем в танке и даже не понимает о чём речь - мы говорим о сортировке массива. Массив - это такая структура данных в которой данные хранятся в индексируемых ячейках. Индексы начинаются с нуля, являются целыми числами и увеличиваются без интервалов. Например 0,1,2,3,4,5,... У массива есть длина - это количество ячеек этого массива. В нашем случае мы будем рассматривать массивы с данными для которых определено отношение порядка - т.е. про любые два элемента можно сказать что один из них либо меньше (раньше), либо больше (позже), либо они равны друг-другу (неразличимы).

Массивы бывает необходимо как-то сортировать по-убыванию или возрастанию некой величины. Например для отображения в интерфейсе истории сообщений от новых к старым. Или сортировки файлов по их размеру. Да и вообще у сортированных данных есть много полезных свойств в плане быстродействия.

Пузырьковая сортировка - это такой метод сортировки (как нам подсказывает КЭП). Суть этого метода очень простая - мы сравниваем 2 соседних элемента, если второй элемент меньше, мы меняем их местами и переходим к следующей паре элементов. При этом методе мы начинаем с первого элемента массива и каждый раз переходим к элементу с индексом на один больше. Если доходим до конца и за этот проход была хотя бы одна перестановка - начинаем проход массива с начала. Таким образом за каждый проход мы "поднимаем" самый большой элемент в самый конец массива. Большие элементы сдвигаются к концу массива, маленькие - к началу. И так до тех пор пока массив не будет полностью отсортирован.

Алгоритм

Будем считать, что исходный массив data уже задан и заполнен. Для простоты будем считать, что массив заполнен числами.

var bubbleSort = function(data) { 
	var changed = true; // задаём флаг, показывающий что за последний проход мы меняли что-то местами
	
	var temp; // вспомогательная переменная для временного хранения данных
	var i; // переменная-счётчик
	var maxIdx = data.lenght - 1; // максимальный индекс для сортировки
	
	while(changed) { // проверяем, что в прошлый раз были изменения
		changed = false; // снимаем флаг изменений
		
		for (i = 0; i < maxIdx; i++) { // проходим по всем индексам массива
			if (data[i] > data[i+1]) { // проверяем, что элементы перепутаны и меняем их местами.
				temp = data[i];
				data[i] = data[i+1];
				data[i+1] = temp;
				changed = true; // помечаем что изменения произошли
			}
		}
	}
	
	return data;
}

Итого у нас получился простой и понятный алгоритм для сортировки. Однако всегда встаёт вопрос - на сколько хорош этого алгоритм?

Немного математики

Подумаем немного на тему того, сколько вообще потребуется сравнений и перестановок, чтобы отсортировать наш массив. Для этого посмотрим на поведение этого алгоритма. Сразу видно, что за один проход мы самый большой элемент передвигаем в самое начало. Если представить, что самый большой элемент находится в самом начале массива, то видно, что при одном проходе он станет последним, а порядок остальных элементов останется неизменным. Таким образом становится ясно, что самый "плохой" набор данных для этого алгоритма - массив упорядоченный по убыванию. При каждом проходе такого массива мы будем перемещать всего один элемент из начала в конец.

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

В нашем случае одна итерация алгоритма - это проверка 2-х переменных и их перестановка в случае необходимости.

Сколько нам потребуется итераций? Обозначим длину массива как n. Каждый проход мы будем совершать по n-1 итераций. Т.к. за каждый проход мы перемещаем только один элемент, то всего потребуется n-1 проходов (последний элемент автоматически окажется на своём месте) Итого потребуется (n-1) * (n-1) = n^2 -2n + 1 итераций. Для достаточно больших n часть n^2 будет значительно больше, чем 2n - 1, так что для описания сложности используют только эту большую часть.

Заметка: при оценке сложности берётся элемент, который быстрее всего растёт с увеличением n.

Для этого достаточно оценить какой элемент будет больше при очень большом значении n. Возьмём например n=10 000, при этом n^2= 100 000 000, а 2n - 1 = 19 999. Очевидно, что при 100 000 000 операций ещё плюс-минус 20 000 практически ничего не изменят в процентном соотношении, поэтому используют только n^2.

Записывается это как O(n^2) - и это является достаточно паршивой оценкой для сложности алгоритма сортировки.

Заметка: сложность пузырьковой сортировки O(n^2).

Алгоритмы со сложностью O(n^2) считаются достаточно медленными алгоритмами. В настоящий момент разработаны оптимизации для большинства алгоритмом, которые либо сводят сложность к O(n), либо хотя бы к O(n * log(n)). Стоит отметить также и отдельный класс задач, для которых даже O(n^2) можно было бы считать просто невероятной оценкой - это так называемые np-полные задачи. Сложность таких задач растёт экспоненциально или даже быстрее: O(e^n). Если быть точнее эти задачи не могут быть решены за полиномиальное время (т.е. например O(n^k), где k - любое число)

Немного оптимизации

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

var bubbleSort = function(data) { 
	var changed = true; // задаём флаг, показывающий что за последний проход мы меняли что-то местами
	
	var temp; // вспомогательная переменная для временного хранения данных
	var i; // переменная-счётчик
	var maxIdx = data.lenght - 1; // максимальный индекс для сортировки
	
	while(changed) { // проверяем, что в прошлый раз были изменения
		changed = false; // снимаем флаг изменений
		
		for (i = 0; i < maxIdx; i++) { // проходим по всем индексам массива
			if (data[i] > data[i+1]) { // проверяем, что элементы перепутаны и меняем их местами.
				temp = data[i];
				data[i] = data[i+1];
				data[i+1] = temp;
				changed = i; // сохраняем индекс последнего изменения
			}
		}
		
		maxIdx = changed; // выставляем последний индекс для следующего прохода
	}
	
	return data;
}

Ещё немного математики

Попробуем оценить на сколько более оптимальным стал наш алгоритм. На каждом проходе нам на придётся рассматривать на один элемент меньше. Количество сравнений будет равно сумме чисел от 1 до n-1 - оставлю это без объяснений, при желании это легко посчитать и доказать. Итого количество сравнений будет (n-1 + 1) * (n - 1) / 2 = (n^2)/2 -n/2 Тут как и в прошлый раз главной частью будет n^2, однако оно идёт с коэффициентом 1/2. Таким образом можно сказать, что новый алгоритм работает в 2 раза быстрее.

Итого

Теперь взглянем внимательно на то, что получилось и попробуем понять, какие свойства у нашего алгоритма.

  1. Наш алгоритм полный - любой массив будет корректно отсортирован.
  2. Наш алгоритм имеет верхнюю границу сложности O(n^2) - сложность при худших условиях (отсортированный по-убыванию массив).
  3. Наш алгоритм имеет нижнюю границу сложности O(n) - сложность при лучших условиях (уже отсортированный по возрастанию).
  4. Наш алгоритм устойчив - равнозначные элементы не поменяются местами.