Сортировка относится к упорядочению данных в определенном формате. Алгоритм сортировки определяет способ упорядочения данных в определенном порядке. Наиболее распространенные заказы в числовом или лексикографическом порядке.
Важность сортировки заключается в том, что поиск данных может быть оптимизирован до очень высокого уровня, если данные хранятся в отсортированном виде. Сортировка также используется для представления данных в более удобочитаемых форматах. Ниже приведены некоторые примеры сортировки в реальных сценариях:
-
Телефонный справочник. В телефонном справочнике хранятся телефонные номера людей, отсортированные по их именам, чтобы их можно было легко найти.
-
Словарь — словарь хранит слова в алфавитном порядке, так что поиск любого слова становится легким.
Телефонный справочник. В телефонном справочнике хранятся телефонные номера людей, отсортированные по их именам, чтобы их можно было легко найти.
Словарь — словарь хранит слова в алфавитном порядке, так что поиск любого слова становится легким.
Сортировка на месте и сортировка на месте
Алгоритмы сортировки могут потребовать дополнительного пространства для сравнения и временного хранения нескольких элементов данных. Эти алгоритмы не требуют дополнительного пространства, и говорят, что сортировка происходит на месте или, например, внутри самого массива. Это называется сортировкой на месте . Пузырьковая сортировка является примером сортировки на месте.
Однако в некоторых алгоритмах сортировки программе требуется пространство, которое больше или равно сортируемым элементам. Сортировка, которая использует одинаковое или большее пространство, называется сортировкой не на месте . Сортировка слиянием является примером сортировки по месту.
Стабильная и не стабильная сортировка
Если алгоритм сортировки после сортировки содержимого не изменяет последовательность аналогичного содержимого, в котором они появляются, это называется стабильной сортировкой .
Если алгоритм сортировки после сортировки содержимого изменяет последовательность аналогичного содержимого, в котором они появляются, это называется нестабильной сортировкой .
Стабильность алгоритма имеет значение, когда мы хотим сохранить последовательность исходных элементов, например, в кортеже.
Адаптивный и неадаптивный алгоритм сортировки
Алгоритм сортировки называется адаптивным, если он использует преимущества уже «отсортированных» элементов в списке, который должен быть отсортирован. То есть при сортировке, если в исходном списке уже есть какой-то элемент, адаптивные алгоритмы примут это во внимание и постараются не переупорядочивать их.
Неадаптивный алгоритм — это алгоритм, который не учитывает элементы, которые уже отсортированы. Они пытаются принудительно переупорядочить каждый элемент, чтобы подтвердить их сортировку.
Важные условия
Некоторые термины, как правило, придуманы при обсуждении методов сортировки, вот краткое введение к ним —
Увеличение заказа
Считается, что последовательность значений находится в возрастающем порядке , если последующий элемент больше предыдущего. Например, 1, 3, 4, 6, 8, 9 расположены в порядке возрастания, поскольку каждый следующий элемент больше, чем предыдущий элемент.
Уменьшение заказа
Последовательность значений называется в порядке убывания , если последующий элемент меньше текущего. Например, 9, 8, 6, 4, 3, 1 расположены в порядке убывания, так как каждый следующий элемент меньше, чем предыдущий элемент.
Неупорядоченный заказ
Считается, что последовательность значений находится в не возрастающем порядке , если последующий элемент меньше или равен своему предыдущему элементу в последовательности. Этот порядок происходит, когда последовательность содержит повторяющиеся значения. Например, 9, 8, 6, 3, 3, 1 расположены в не возрастающем порядке, поскольку каждый следующий элемент меньше или равен (в случае 3), но не больше, чем любой предыдущий элемент.
Неубывающий Заказ
Считается, что последовательность значений находится в неубывающем порядке , если последующий элемент больше или равен своему предыдущему элементу в последовательности. Этот порядок происходит, когда последовательность содержит повторяющиеся значения. Например, 1, 3, 3, 6, 8, 9 расположены в неубывающем порядке, так как каждый следующий элемент больше или равен (в случае 3), но не меньше, чем предыдущий.