компонентов
Бояться не надо
Сортировка - упорядочивание чисел в массиве, в котором первоначально элементы расположены в случайном порядке. Сортировка может быть выполнена как по возрастанию значения элементов, так и по их убыванию. Сортировка важна и очень часто применяется в базах данных, так как поиск информации в упорядоченном массиве происходит гораздо быстрее.
Так как в задачах поиска операцию сортировки приходится выполнять многократно для очень больших объёмов данных, то критическое значение имеет время сортировки. Поэтому эффективность алгоритма сортировки имеет очень важное значение. Разработано множество алгоритмов сортировки, отличающихся эффективностью в тех или иных наборах данных.
На странице Работа с объектом StringList была рассмотрена сортировка чисел с помощью такого объекта как StringList. Сортировка в StringList'е универсальна, достаточно эффективна, и лишь в два раза медленнее так называемой "быстрой" сортировки. Для сравнения, рассмотрим и некоторые другие алгоритмы сортировки.
Сортировка пузырьком - самый естественный, он же самый медленный алгоритм сортировки. Массив чисел просматривается от начала до конца до тех пор, пока любые два рядом стоящих числа не будут расположены по возрастанию. Для этого два неверно расположенные одно относительно другого числа меняются местами. При этом наименьшее число, как пузырёк, постепенно всплывает к началу массива ( а наибольшее сразу "тонет" как камень!), отсюда и название алгоритма. Время сортировки пузырьком растёт пропорционально квадрату роста количества элементов в массиве.
Сортировка вставками - ещё один простой способ сортировки. Массив чисел сортируется с начала, и каждое последующее число вставляется в уже отсортированную часть массива на предназначенное ему место. Таким образом, новое число сравнивается и при необходимости меняется местами не со всеми числами в массиве, а только до тех пор, пока в уже отсортированной части массива не найдется меньшее его число. Поэтому сортировка вставками примерно в два раза быстрее сортировки пузырьком. А для уже частично отсортированных массивов сортировка вставками - наилучший метод сортировки. Время сортировки вставками также пропорционально квадрату количества элементов.
Быстрая сортировка - очень эффективный алгоритм, и известна как в среднем самая быстрая из универсальных алгоритмов сортировки. Быстрая сортировка сравнивает все элементы массива с одним, выбранным практически наугад, элементом (опорным элементом) и тем самым делит массив на две части - в одну попадают числа меньшие опорного, а в другую - большие опорного. Затем каждая из этих двух частей также подвергается аналогичной сортировке, и так до тех пор, пока очередная часть не окажется состоящей из единственного элемента. Время сортировки пропорционально логарифму от количества элементов.
Программа, позволяющая на практике сравнить между собой эффективность этих алгоритмов сортировки, представлена ниже.
Сначала необходимо задать количество элементов в массиве, и нажать кнопку "Заполнить". Таблица заполняется случайными числами в диапазоне 0 - 999 999. Лично мне не удалось создать таблицу, содержащую более миллиона чисел. Можно также загрузить массив из файла, или выгрузить готовый массив в файл (однако массив из более чем 540 000 элементов загрузить не удаётся...). Далее можно выбрать желаемый метод сортировки, затем нажать кнопку "Сортировать". Во время сортировки продолжительность в секундах отображается в заголовке окна. Предупреждаю, что выбрав для сортировки миллиона чисел метод пузырька, окончания процесса можно не дождаться - я ждал 54 минуты! Что касается сортировки вставкой, то миллион чисел она сортировала 17 минут! Модификация алгоритма сортировки вставками, ищущая место вставок с помощью метода половинного деления, сокращает время сортировки до 7 минут.