Приветствую Вас на сайте Info-Comp.ru! Сегодня мы с Вами поговорим об одном очень популярном алгоритме, который встречается в процессе изучения программирования, – это «Сортировка пузырьком», в частности мы реализуем данный алгоритм на языке T-SQL.
Сразу хотелось бы отметить, что даже в классическом программировании данный алгоритм сортировки в большей степени является учебным, т.е. используется только для изучения алгоритмов, а в реальной работе практически не используется, так как существуют более эффективные алгоритмы сортировки, и, конечно же, в большинстве случаев все они уже реализованы и включаются в инструменты программирования.
Если говорить в отношении программирования баз данных, то алгоритмы сортировки здесь не требуются, так как язык SQL, который используется для работы с данными в реляционных базах данных, работает со множеством, т.е. с таблицами, и стандартом этого языка определена инструкция ORDER BY, которая и позволяет сортировать данные в таблицах.
Поэтому не ищите какой-то практической составляющей в данной статье, я попытался реализовать алгоритм «Сортировка пузырьком» на T-SQL только для того, чтобы посмотреть, как же он будет выглядеть на данном языке, т.е. ради интереса)) Дело в том, что примеров реализации данного алгоритма на других языках полно, а на T-SQL таких примеров нет.
Заметка! Как получить последовательность дат в указанном промежутке на T-SQL.
Описание алгоритма «Сортировка пузырьком»
Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов.
Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован.
В результате каждого прохода на последнее место в массиве сдвигается элемент с максимальным значением и не учитывается при следующем проходе, так как данная часть массива уже отсортирована.
Таким образом, после каждого прохода элемент с максимальным значением в неотсортированной части массива ставится в конце массива рядом с максимальным значением, которое было в предыдущем проходе, а элемент с наименьшим значением перемещается на одну позицию к началу массива, и как результат «всплывает» до нужной позиции, как пузырёк в воде — отсюда и название алгоритма.
Реализация алгоритма «Сортировка пузырьком» на T-SQL
На а теперь давайте перейдём к реализации алгоритма «Сортировка пузырьком» на языке T-SQL в Microsoft SQL Server.
В качестве исходных данных у меня будет выступать массив чисел, который представлен на картинке чуть выше, т.е. алгоритм ниже выполняет те же самые действия, что и на GIF изображении.
Для удобства данный алгоритм я оформил в виде хранимой процедуры bubble_sort.
Весь код я подробно прокомментировал.
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;
Как видим, данные отсортированы.
Заметка! Проверка знаний языка T-SQL в формате онлайн-тестирования.
На сегодня это все, надеюсь, материал был Вам интересен, пока!