Сортування бульбашкою на t-sql-приклад реалізації алгоритму

14

Вітаю вас на сайті info-comp.ru! сьогодні ми з вами поговоримо про один дуже популярному алгоритмі, який зустрічається в процесі вивчення програмування, – це «сортування бульбашкою», зокрема ми реалізуємо даний алгоритм на мові t-sql.

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

Якщо говорити щодо програмування баз даних, то алгоритми сортування тут не потрібні, так як мова sql, який використовується для роботи з даними в реляційних базах даних, працює з безліччю, тобто. З таблицями, і стандартом цієї мови визначена інструкція order by, яка і дозволяє сортувати дані в таблицях.

Тому не шукайте якоїсь практичної складової в даній статті, я спробував реалізувати алгоритм «сортування бульбашкою» на 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.

exec bubble_sort;

Як бачимо, дані відсортовані.