Сортировка пузырьком на T-SQL – пример реализации алгоритма

Приветствую Вас на сайте Info-Comp.ru! Сегодня мы с Вами поговорим об одном очень популярном алгоритме, который встречается в процессе изучения программирования, – это «Сортировка пузырьком», в частности мы реализуем данный алгоритм на языке T-SQL.

Сортировка пузырьком на T-SQL – пример реализации алгоритма

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

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

Поэтому не ищите какой-то практической составляющей в данной статье, я попытался реализовать алгоритм «Сортировка пузырьком» на T-SQL только для того, чтобы посмотреть, как же он будет выглядеть на данном языке, т.е. ради интереса)) Дело в том, что примеров реализации данного алгоритма на других языках полно, а на T-SQL таких примеров нет.

Заметка! Как получить последовательность дат в указанном промежутке на T-SQL.

Описание алгоритма «Сортировка пузырьком»

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов.

Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован.

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

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

Скриншот 1

Реализация алгоритма «Сортировка пузырьком» на T-SQL

На а теперь давайте перейдём к реализации алгоритма «Сортировка пузырьком» на языке T-SQL в Microsoft SQL Server.

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

Для удобства данный алгоритм я оформил в виде хранимой процедуры bubble_sort.

Заметка! Назначение хранимых процедур в языке T-SQL.

Весь код я подробно прокомментировал.

   
   CREATE PROCEDURE bubble_sort
   AS 
   BEGIN
	--Табличная переменная для хранения массива данных с числами
	--Индекс массива начинается с 0
	DECLARE @data_array TABLE (array_index INT NOT NULL IDENTITY(0, 1) PRIMARY KEY,
				   value INT NOT NULL);
	--Добавление данных в табличную переменную
	INSERT INTO @data_array
		VALUES (5),(2),(1),(3),(9),(0),(4),(6),(8),(7);
		
	--Вывод данных до сортировки
	SELECT array_index, value
	FROM @data_array;

	DECLARE @current_element INT, --Текущий элемент в массиве
		@amount_elements INT, --Количество элементов в массиве
		@continue_sort BIT;   --Признак для продолжения сортировки
	
	--Переменные для хранения значений массива
	DECLARE @value1 INT, 
		@value2 INT;

	--Определяем количество элементов в массиве, учитывая, что он начинается с 0
	SELECT @amount_elements = COUNT(*) - 1
	FROM @data_array;
	
	SET @continue_sort = 1;
	
	/*
		@continue_sort = 1 - продолжать сортировку, массив не отсортирован
		@continue_sort = 0 - сортировка завершена, массив отсортирован
	*/
	
	--Запуск цикла для прохода по массиву
	WHILE @continue_sort = 1
	BEGIN
		--Сразу отмечаем, что сортировку нужно завершить, в случае если не будет обмена значениями
		SET @continue_sort = 0;
		
		--Проход по массиву начинаем с первого элемента
		SET @current_element = 0;
		
		--Запуск цикла для сравнения значений массива в текущем проходе
		WHILE @current_element < @amount_elements
		BEGIN

			SELECT @value1 = 0,
			       @value2 = 0;
			
			--Получаем первые значения в массиве
			SELECT @value1 = value 
			FROM @data_array 
			WHERE array_index = @current_element;

			SELECT @value2 = value 
			FROM @data_array 
			WHERE array_index = @current_element + 1;
			
			--Сравнение значений
			--Если первое значение больше второго, то необходимо поменять их местами
			IF @value1 > @value2 
			BEGIN
				UPDATE @data_array SET value = @value2
				WHERE array_index = @current_element;

				UPDATE @data_array SET value = @value1
				WHERE array_index = @current_element + 1;
				
				--Произошел обмен значениями, значит сортировку следует продолжать
				SET @continue_sort = 1;
			END
			
			--Двигаемся дальше по массиву
			SET @current_element = @current_element + 1;
		END
	/*
		После прохода по массиву в его конце оказываются отсортированные элементы
		Исключаем их, для уменьшения количества интераций (сравнений)
	*/
	SET @amount_elements = @amount_elements - 1;

	END
	
	--Вывод данных после сортировки
	SELECT array_index, value
	FROM @data_array;

   END

   GO

Чтобы проверить работу алгоритма, вызываем процедуру bubble_sort.

Заметка! Если Вас интересует язык SQL, то рекомендую почитать книгу «SQL код» – это самоучитель по языку SQL для начинающих программистов. В ней язык SQL рассматривается как стандарт, чтобы после прочтения данной книги можно было работать с языком SQL в любой системе управления базами данных.

   
   EXEC bubble_sort;

Скриншот 2

Как видим, данные отсортированы.

Заметка! Проверка знаний языка T-SQL в формате онлайн-тестирования.

На сегодня это все, надеюсь, материал был Вам интересен, пока!

Понравилась статья? Поделиться с друзьями:
Заметки IT специалиста
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!:
Нажимая на кнопку «Отправить комментарий», я даю согласие на обработку персональных данных и принимаю политику конфиденциальности.