Програмісти, які переходять з ПК та веб-розробки на кодування для мобільних пристроїв або вбудованих систем, виявляють, що більше часу витрачається на вибір і кодування власних структур даних і алгоритмів. З меншою пам’яттю та обмеженим сховищем даних немає місця для попередньо створених бібліотек чи фреймворків. Тому для тих, кому потрібно написати власні процедури сортування, ось кілька міркувань щодо вибору низького бульбашкового сортування.
Фон
Бульбашкове сортування — це простий алгоритм, який сортує список елементів у пам’яті. За допомогою масиву код багаторазово порівнює кожну пару суміжних елементів і міняє їх місцями, якщо вони не в порядку. Процес повторюється до тих пір, поки не перестане відбуватися заміна. Якби можна було переглядати масив під час сортування, низькі значення «виникали б» угору, а великі значення опускалися б вниз. Ось відповідний код у Visual Basic 2010:
Відео дня
Хоча swap = True swap = False Для i = 0 До tbl.length - 2 Якщо tbl (i) > tbl (i + 1) Тоді tmp = tbl (i) tbl (i) = tbl (i + 1) tbl (i + 1) = tmp swap = True End, якщо наступний кінець Хоча
Коли вибрати бульбашковий сорт
Цей алгоритм має ряд переваг. Його легко написати, легко зрозуміти, і для цього потрібно всього кілька рядків коду. Дані сортуються на місці, тому є мало накладних витрат на пам’ять, і після сортування дані знаходяться в пам’яті, готові до обробки. Основним недоліком є кількість часу, необхідного для сортування. Середній час зростає майже в геометричній прогресії зі збільшенням кількості елементів таблиці. Десятикратна кількість елементів сортування займає майже в сто разів більше часу.
Інші сорти масивів
Алгоритми сортування відрізняються за складністю, швидкістю та накладними витратами. Пухирчастий сорт є найменш складним, але також одним із найповільніших. Інші сортування на основі масиву, такі як сортування вставкою та сортування обміном, працюють трохи швидше, але потребують більше коду (див. посилання нижче). Основна перевага сортування на основі масивів полягає в тому, що вони використовують найменшу кількість коду та займають найменший обсяг робочої пам’яті. Розглянемо ці сорти для простих масивів з менш ніж кількома сотнями елементів.
Складні алгоритми сортування
Більші набори даних вимагають складнішого коду та більше пам’яті. Швидке сортування та сортування в купі розбивають і копіюють набори даних для оптимізації кількості порівнянь. Швидке сортування безперервно розділяє список, а потім знову збирає його в упорядкованому порядку. Сортування в купі копіює дані в деревоподібну структуру, а потім обходить дерево, щоб скопіювати дані назад у порядок. Обидва швидкі та ефективні, але потребують більше коду та набагато більше робочого сховища. Виберіть ці алгоритми для великих наборів даних.
