Преимущества и недостатки пузырьковой сортировки

Программисты, которые переключаются с ПК и веб-разработки на кодирование для мобильных устройств или встроенных систем, обнаруживают, что больше времени тратится на выбор и кодирование собственных структур данных и алгоритмов. При меньшем объеме памяти и ограниченном хранилище данных нет места для готовых библиотек или фреймворков. Итак, для тех, кому нужно написать свои собственные процедуры сортировки, вот несколько соображений по выбору низкоуровневой пузырьковой сортировки.

​​Фон

Пузырьковая сортировка — это простой алгоритм, который сортирует список элементов в памяти. При заданном массиве код неоднократно сравнивает каждую пару соседних элементов и меняет их местами, если они не в порядке. Процесс повторяется до тех пор, пока не перестанут происходить обмены. Если бы можно было просматривать массив во время сортировки, то низкие значения «поднимались бы вверх», а большие — опускались бы вниз. Вот соответствующий код в 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

Когда следует выбирать пузырьковую сортировку

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

Другие сортировки массивов

Алгоритмы сортировки различаются по сложности, скорости и накладным расходам. Пузырьковая сортировка является наименее сложной, но и одной из самых медленных. Другие сортировки на основе массивов, такие как сортировка вставками и сортировка обменом, немного быстрее, но требуют больше кода (см. ссылки ниже). Основное преимущество сортировки на основе массива заключается в том, что она использует наименьший объем кода и занимает наименьший объем рабочей памяти. Используйте эти сортировки для простых массивов, содержащих менее нескольких сотен элементов.

Сложные алгоритмы сортировки

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