Сортировка выбором: принцип работы и особенности

Введение

Алгоритм сортировки

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

Сравнение с другими алгоритмами сортировки

Среди алгоритмов квадратичной сортировки (сортировочные алгоритмы со средней сложностью Θ(n2)) сортировка выбором почти всегда превосходит сортировку пузырьком и сортировку гномом. Сортировка вставками очень похожа в том, что после k-й итерации первые элементы в массиве оказываются отсортированными. Преимущество сортировки вставками заключается в том, что она просматривает только столько элементов, сколько необходимо для размещения s-го элемента, в то время как сортировка выбором должна просматривать все оставшиеся элементы, чтобы найти s-й элемент. Простой подсчет показывает, что сортировка вставками обычно выполняет примерно вдвое меньше сравнений, чем сортировка выбором, хотя количество сравнений может быть таким же или значительно меньше в зависимости от исходного порядка элементов в массиве. Для некоторых приложений реального времени может быть преимуществом то, что сортировка выбором работает одинаково независимо от исходного порядка массива, в то время как время выполнения сортировки вставками может существенно меняться. Однако чаще это является преимуществом для сортировки вставками, поскольку она работает гораздо эффективнее, если массив уже отсортирован или "близок к отсортированному". Хотя сортировка выбором предпочтительнее сортировки вставками с точки зрения количества операций записи (обмены против до обменов, при этом каждый обмен состоит из двух записей), это примерно в два раза больше теоретического минимума, достигаемого сортировкой циклами, которая выполняет не более n операций записи. Это может быть важно, если операции записи значительно дороже операций чтения, например, при использовании EEPROM или флэш-памяти, где каждая запись сокращает срок службы памяти. Сортировку выбором можно реализовать без непредсказуемых переходов для повышения эффективности предсказателя переходов процессора, находя местоположение минимального элемента с помощью кода, не содержащего переходов, а затем выполняя обмен безусловно. Наконец, на больших массивах сортировка выбором значительно уступает алгоритмам "разделяй и властвуй", таким как сортировка слиянием. Однако сортировка вставками или сортировка выбором обычно быстрее для небольших массивов (то есть, содержащих менее 10–20 элементов). Практичным способом оптимизации рекурсивных алгоритмов является переключение на сортировку вставками или сортировку выбором для "достаточно маленьких" подмассивов.

Among quadratic sorting algorithms (sorting algorithms with a simple average case of Θ(n2)), selection sort almost always outperforms bubble sort and gnome sort. Insertion sort is very similar in that after the kth iteration, the first elements in the array are in sorted order. Insertion sort's advantage is that it only scans as many elements as it needs in order to place the st element, while selection sort must scan all remaining elements to find the st element. Simple calculation shows that insertion sort will therefore usually perform about half as many comparisons as selection sort, although it can perform just as many or far fewer depending on the order the array was in prior to sorting. It can be seen as an advantage for some real time applications that selection sort will perform identically regardless of the order of the array, while insertion sort's running time can vary considerably. However, this is more often an advantage for insertion sort in that it runs much more efficiently if the array is already sorted or "close to sorted." While selection sort is preferable to insertion sort in terms of number of writes ( swaps versus up to swaps, with each swap being two writes), this is roughly twice the theoretical minimum achieved by cycle sort, which performs at most n writes. This can be important if writes are significantly more expensive than reads, such as with EEPROM or Flash memory, where every write lessens the lifespan of the memory. Selection sort can be implemented without unpredictable branches for the benefit of CPU branch predictors, by finding the location of the minimum with branch free code and then performing the swap unconditionally. Finally, selection sort is greatly outperformed on larger arrays by divide and conquer algorithms such as mergesort. However, insertion sort or selection sort are both typically faster for small arrays (i. e. fewer than 10–20 elements). A useful optimization in practice for the recursive algorithms is to switch to insertion sort or selection sort for "small enough" sublists.