Алгоритм сортировки — это алгоритм
для упорядочения элементов в списке. В случае, когда элемент списка
имеет несколько полей, поле, служащее критерием порядка, называется
ключом сортировки. На практике, в качестве ключа часто выступает число,
а в остальных полях хранятся какие-либо данные, никак не влияющие на
работу алгоритма.
Оценка алгоритма сортировки
Единственного эффективнейшего алгоритма сортировки нет, ввиду множества параметров оценки эффективности:
Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее
поведение алгоритма в терминах размера списка (n). Для типичного
алгоритма хорошее поведение — это O(n log n) и плохое поведение — это
O(n²). Идеальное поведение для упорядочения — O(n). Алгоритмы
сортировки, использующие только абстрактную операцию сравнения ключей
всегда нуждаются по меньшей мере в O(n log n) сравнениях в среднем;
Память — ряд алгоритмов требует выделения дополнительной
памяти под временное хранение данных. При оценке используемой памяти не
будет учитываться место, которое занимает исходный массив и независящие
от входной последовательности затраты, например, на хранение кода
программы.
Естественность поведения — эффективность метода при
обработке уже упорядоченных, или частично упорядоченных данных.
Алгоритм ведёт себя естественно, если учитывает эту характеристику
входной последовательности и работает лучше.
