Структура данных - методы сортировки
Сортировка относится к расположению данных в определенном формате. Алгоритм сортировки определяет способ упорядочивания данных в определенном порядке. Чаще всего заказывается в числовом или лексикографическом порядке.
Важность сортировки заключается в том, что поиск данных можно оптимизировать до очень высокого уровня, если данные хранятся в отсортированном виде. Сортировка также используется для представления данных в более удобочитаемых форматах. Ниже приведены некоторые примеры сортировки в реальных сценариях.
Telephone Directory - В телефонном справочнике хранятся телефонные номера людей, отсортированные по именам, что упрощает поиск по именам.
Dictionary - Словарь хранит слова в алфавитном порядке, поэтому поиск любого слова становится легким.
Сортировка на месте и сортировка без места
Алгоритмам сортировки может потребоваться дополнительное пространство для сравнения и временного хранения нескольких элементов данных. Эти алгоритмы не требуют дополнительного места, и говорят, что сортировка происходит на месте или, например, внутри самого массива. Это называетсяin-place sorting. Пузырьковая сортировка - это пример сортировки на месте.
Однако в некоторых алгоритмах сортировки программе требуется пространство, которое больше или равно сортируемым элементам. Сортировка, использующая равное или большее пространство, называетсяnot-in-place sorting. Сортировка слиянием - это пример сортировки не по месту.
Стабильная и нестабильная сортировка
Если алгоритм сортировки после сортировки содержимого не изменяет последовательность аналогичного содержимого, в котором они появляются, он называется stable sorting.
Если алгоритм сортировки после сортировки содержимого изменяет последовательность аналогичного содержимого, в котором они появляются, он называется unstable sorting.
Стабильность алгоритма имеет значение, когда мы хотим сохранить последовательность исходных элементов, например, в кортеже.
Адаптивный и неадаптивный алгоритм сортировки
Алгоритм сортировки называется адаптивным, если он использует уже «отсортированные» элементы в списке, который нужно отсортировать. То есть, при сортировке, если в исходном списке есть уже отсортированный элемент, адаптивные алгоритмы учтут это и постараются не переупорядочивать их.
Неадаптивный алгоритм - это алгоритм, который не учитывает уже отсортированные элементы. Они пытаются принудительно переупорядочить каждый элемент, чтобы подтвердить их сортировку.
Важные термины
Некоторые термины обычно используются при обсуждении методов сортировки, вот краткое введение в них -
Возрастающий порядок
Говорят, что последовательность значений находится в increasing order, если следующий элемент больше предыдущего. Например, 1, 3, 4, 6, 8, 9 находятся в порядке возрастания, поскольку каждый следующий элемент больше предыдущего.
Убывающий порядок
Говорят, что последовательность значений находится в decreasing order, если следующий элемент меньше текущего. Например, 9, 8, 6, 4, 3, 1 находятся в порядке убывания, поскольку каждый следующий элемент меньше предыдущего.
Неувеличивающийся порядок
Говорят, что последовательность значений находится в non-increasing order, если последующий элемент меньше или равен своему предыдущему элементу в последовательности. Этот порядок возникает, когда последовательность содержит повторяющиеся значения. Например, 9, 8, 6, 3, 3, 1 находятся в невозрастающем порядке, поскольку каждый следующий элемент меньше или равен (в случае 3), но не больше любого предыдущего элемента.
Неубывающий порядок
Говорят, что последовательность значений находится в non-decreasing order, если последующий элемент больше или равен своему предыдущему элементу в последовательности. Этот порядок возникает, когда последовательность содержит повторяющиеся значения. Например, 1, 3, 3, 6, 8, 9 находятся в порядке неубывания, так как каждый следующий элемент больше или равен (в случае 3), но не меньше предыдущего.