Программисты, которые переключаются с ПК и веб-разработки на кодирование для мобильных устройств или встроенных систем, обнаруживают, что больше времени тратится на выбор и кодирование собственных структур данных и алгоритмов. При меньшем объеме памяти и ограниченном хранилище данных нет места для готовых библиотек или фреймворков. Итак, для тех, кому нужно написать свои собственные процедуры сортировки, вот некоторые соображения по выбору простой пузырьковой сортировки.
Фон
Пузырьковая сортировка - это простой алгоритм, который сортирует список элементов в памяти. Учитывая массив, код многократно сравнивает каждую пару соседних элементов и меняет их местами, если они не в порядке. Процесс повторяется до тех пор, пока не перестанут происходить перестановки. Если бы можно было просматривать массив во время сортировки, низкие значения «пузырились бы» вверх, а большие значения опускались бы вниз. Вот соответствующий код в Visual Basic 2010:
Видео дня
Пока swap = True swap = False For i = 0 To tbl.length - 2 Если tbl (i)> tbl (i + 1) Тогда tmp = tbl (i) tbl (i) = tbl (i + 1) tbl (i + 1) = tmp swap = True End If Next End While
Когда выбирать пузырьковую сортировку
У этого алгоритма есть несколько преимуществ. Его просто написать, легко понять, и он занимает всего несколько строк кода. Данные сортируются на месте, поэтому накладные расходы на память незначительны, и после сортировки данные находятся в памяти и готовы к обработке. Главный недостаток - время, необходимое для сортировки. Среднее время увеличивается почти экспоненциально с увеличением количества элементов таблицы. Чтобы отсортировать в десять раз большее количество элементов, требуется почти в сто раз больше времени.
Другие сортировки массивов
Алгоритмы сортировки различаются по сложности, скорости и накладным расходам. Пузырьковая сортировка наименее сложна, но также одна из самых медленных. Другие сортировки на основе массивов, такие как сортировка вставкой и сортировка обмена, немного быстрее, но требуют больше кода (см. Ссылки ниже). Основное преимущество сортировки на основе массивов состоит в том, что они используют наименьшее количество кода и занимают наименьший объем рабочей памяти. Рассмотрим эти сортировки для простых массивов, содержащих менее нескольких сотен элементов.
Сложные алгоритмы сортировки
Для больших наборов данных требуется более сложный код и больше памяти. Быстрая сортировка и сортировка кучи разделяют и копируют наборы данных для оптимизации количества сравнений. Быстрая сортировка постоянно делит список, а затем снова собирает его в отсортированном порядке. Сортировка кучи копирует данные в древовидную структуру, а затем просматривает дерево, чтобы скопировать данные обратно в порядок. Оба они быстры и эффективны, но требуют больше кода и гораздо больше места для хранения. Выбирайте эти алгоритмы для больших наборов данных.
