Доброго времени суток! В этой статье я расскажу о простой оптимизации алгоритма пузырьковой сортировки (bubble sort), пример простейшей реализации которого я приводил в предыдущей статье (рекомендую прочесть, чтобы понять суть данной стать). Идея данной оптимизации заключается в сокращении избыточных итераций, т. е. поочередных переборов элементов исходного массива. Работать (давать положительный результат) данная модификация алгоритма будет только в том случае, когда избыточные итерации действительно присутствуют (например, попался почти отсортированный массив). Ниже, приведен результат выполнения программы из предыдущей статьи, с массивом, который практически отсортирован. В консоль выводится массив до сортировки, и после каждого перебора его элементов (и видные перестановки его элементов, выполненные во время каждой из итераций).

Доброго времени суток! В этой статье я расскажу об алгоритме сортировки массивов, достаточно простом и не самом эффективном (причем, далеко не самом), но тем не менее, для изучения базовых алгоритмов (в данном случае сортировки), разобрать его будет весьма полезно для начинающих программистов. Сортировка, реализованная по данному алгоритму, называется «пузырьковая сортировка» (bubble sort).

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

Таким образом, если мы, например, сортируем массив целых чисел по возрастанию, по после первого же перебора всех элементов, самый большой элемент окажется в конце массива. После второго перебора, второй по величине элемент станет предпоследним, и т.д.