Алгоритм сортировки, в информатике — процедура упорядочивания элементов в списке путем повторения последовательности шагов. Алгоритмы сортировки позволяют отсортировать список элементов таким образом, чтобы он стал более удобным для использования, чем был, обычно путем размещения элементов в числовом порядке (от наименьшего значения к наибольшему или наоборот) или лексикографическом порядке (также называемом словарным порядком, обобщением алфавитного порядка). Алгоритмы сортировки являются важнейшей составной частью многих других приложений, включая поисковые инструменты, анализ данных и электронную коммерцию. Существует множество алгоритмов сортировки, но в большинстве приложений используются сортировки с относительно низкой вычислительной сложностью — например, Quicksort или merge sort.
В информатике алгоритм — это процедура решения вычислительной задачи. Для того чтобы проблема решалась с помощью алгоритма, она должна быть четко определена, чтобы можно было оценить точность алгоритма. В случае с сортировкой это, как правило, несложно, поскольку элементы обычно сортируются одним из двух четко определенных способов. Один из способов — это числовой порядок, который основан на некотором числовом значении, которым обладают элементы. Сортировка дат от самой ранней к самой поздней, сортировка врачей по рейтингу пациентов от самого высокого к самому низкому или сортировка товаров для продажи в магазине от самого дешевого к самому дорогому — все это примеры числовой сортировки. Другим распространенным способом сортировки является лексикографический порядок, или порядок по словарю, — именно так обычно сортируются буквенно-цифровые значения строк. В большинстве случаев это эквивалентно алфавитному порядку, хотя для сортировки словарей элементов можно использовать и другие правила.
Одним из основных способов оценки алгоритмов сортировки является их вычислительная сложность — мера того, сколько времени и памяти требуется для работы конкретного алгоритма. Поскольку фактические затраты времени и пространства зависят от специфики решаемой задачи (например, сортировка ста элементов или миллиона), компьютерные ученые используют нотацию big-O для описания того, как быстро растут затраты ресурсов по мере увеличения размера задачи. Буква O в нотации big-O обозначает порядок, или вид, роста функции. Например, O(1) означает, что сложность алгоритма постоянна, а O(n) означает, что сложность задачи линейно растет с увеличением n, где n — переменная, связанная с размером задачи, например, длина списка, который нужно отсортировать. Значение O конкретного алгоритма может также зависеть от специфики задачи, поэтому его иногда анализируют для наилучшего, наихудшего и среднего сценариев.
Алгоритмы сортировки можно описать несколькими способами. Некоторые алгоритмы являются стабильными, то есть порядок эквивалентных элементов сохраняется, другие — нестабильными, то есть порядок может не сохраняться. Например, если база данных личных контактов отсортирована сначала по имени, а затем по адресу, стабильный алгоритм сортировки обеспечит сохранение алфавита людей, живущих по одному и тому же адресу, по имени в пределах каждого адреса.
Алгоритмы сортировки также можно разделить на алгоритмы сравнения, которые сортируют, сравнивая один элемент списка с другим, и алгоритмы без сравнения, которые находят другие способы сортировки. Несравнительные алгоритмы иногда менее сложны в вычислениях, чем даже самые лучшие алгоритмы сравнения, но они часто ограничены в других отношениях. Например, счетная сортировка требует меньше времени, чем любая сравнительная сортировка, но может применяться только к целым числам. Приведенные ниже примеры являются алгоритмами сравнения.
One simple sorting algorithm is known as selection sort. In this algorithm, the sort function analyzes an unsorted list to find the first element—typically the minimum—then swaps it with the first element in the list. It then analyzes the unsorted part of the list again to find the new minimum element and swaps it with the first element in the unsorted part of the list. It repeats this process until each element in the list has been sorted. For example, consider the list {8,5,1,3,7}. The algorithm sorts the list into {1,5,8,3,7} by switching the 8 and the 1 and continues until the list is completely sorted.
Сортировка по выбору относительно интуитивна и напоминает то, как многие люди сортируют элементы в своей повседневной жизни. Однако она также сложна с вычислительной точки зрения. Каждый элемент списка должен пройти через весь список, и во время каждого прохода каждый неотсортированный элемент должен быть оценен, чтобы найти минимум. Следовательно, сортировка по выбору занимает O(n2), или квадратичное время, где n — длина списка. Это обозначение означает, что время, необходимое для сортировки списка, растет пропорционально квадрату длины списка.
A similar sorting method, insertion sort, involves building a sorted list at the beginning of the unsorted list. Each element in the unsorted list is inserted in its correct place in the sorted list. In the list {8,5,1,3,7}, the first step is to place the 5 before the 8 to make {5,8,1,3,7}.
Как и сортировка выбором, сортировка вставкой в среднем занимает O(n2) времени, но в лучшем случае она намного быстрее, чем сортировка выбором. Для уже отсортированного списка сортировка вставкой использует время O(n), поскольку для определения места элемента в списке она должна сравнивать каждый элемент только с предыдущим.
A more efficient algorithm than insertion sort is merge sort. Merge sort uses a divide-and-conquer approach, splitting an unsorted list into two sublists and continuing to split the sublists in that fashion until each has one or fewer elements. Then the algorithm iteratively merges the sublists in sorted order until the entire list is sorted. The list {8,5,1,3,7} is thus split into five sublists of one element each that are then merged back into one sorted list.
Для сортировки слиянием требуется время O(n logn), что значительно эффективнее, чем O(n2). Необходимое время растет с увеличением длины списка, умноженной на log, или логарифм длины, потому что количество необходимых итераций зависит от того, сколько раз список нужно разделить пополам.
Another popular divide-and-conquer sort algorithm is Quicksort. In Quicksort, one of the values in a list is chosen as a “pivot.” Each other value on the list is then compared with the pivot and placed either before it, if it is smaller, or after it, if it is greater. Then a new pivot is chosen for each of the unsorted sublists, and they are organized in the same fashion. This process is repeated until the entire list is sorted. In the list {8,5,1,3,7}, 1 may be chosen as the pivot, resulting in {1,8,5,3,7}. The number 5 may be chosen as the next pivot, leading to {1,3,5,8,7}, and, with 8 as the next pivot, the list is fully sorted.
В отличие от сортировки слиянием, вычислительная сложность Quicksort сильно зависит от существующего порядка в сортируемом списке. В большинстве случаев Quicksort, как и merge sort, занимает в среднем O(n logn) времени. Однако если список упорядочен в обратном порядке (например, от наибольшего к наименьшему, когда предполагается сортировать от наименьшего к наибольшему), Quicksort использует время O(n2).
