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

Введение

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

Сортировка вставками — это простой алгоритм сортировки, который строит окончательно отсортированный массив (или список) по одному элементу за раз, выполняя сравнения. Он значительно менее эффективен для больших списков, чем более продвинутые алгоритмы, такие как быстрая сортировка, сортировка кучей или сортировка слиянием. Однако сортировка вставками обладает рядом преимуществ:

Простая реализация: Джон Бентли демонстрирует версию на C/C++ в три строки, которая становится пятистрочной при оптимизации.

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

Сортировка вставками очень похожа на сортировку выбором. Как и в сортировке выбором, после k проходов по массиву первые k элементов будут отсортированы. Однако принципиальное различие между этими двумя алгоритмами заключается в том, что сортировка вставками просматривает массив в обратном направлении от текущего ключа, а сортировка выбором – в прямом. В результате сортировка выбором помещает первые k элементов в качестве k наименьших элементов несортированной части входных данных, в то время как сортировка вставками просто помещает первые k элементов входных данных в отсортированный порядок. Основное преимущество сортировки вставками перед сортировкой выбором заключается в том, что сортировка выбором всегда должна просматривать все оставшиеся элементы, чтобы найти наименьший элемент в несортированной части списка, в то время как сортировка вставками требует только одного сравнения, когда (k+1)-й элемент больше, чем k-й элемент; когда это часто происходит (например, если входной массив уже отсортирован или частично отсортирован), сортировка вставками значительно эффективнее сортировки выбором. В среднем (при условии, что ранг (k+1)-го элемента случаен) сортировка вставками потребует сравнения и сдвига половины предыдущих k элементов, то есть сортировка вставками выполнит примерно вдвое меньше сравнений, чем сортировка выбором. В худшем случае для сортировки вставками (когда входной массив отсортирован в обратном порядке) сортировка вставками выполняет столько же сравнений, сколько сортировка выбором. Однако недостатком сортировки вставками по сравнению с сортировкой выбором является то, что она требует больше операций записи, поскольку на каждой итерации вставка (k+1)-го элемента в отсортированную часть массива требует множества обменов элементов для сдвига всех последующих элементов, в то время как для каждой итерации сортировки выбором требуется только один обмен. В общем случае сортировка вставками будет записывать в массив O(n²) раз, в то время как сортировка выбором – только O(n) раз. По этой причине сортировка выбором может быть предпочтительнее в случаях, когда запись в память значительно дороже чтения, например, при использовании EEPROM или флэш-памяти. Хотя некоторые алгоритмы «разделяй и властвуй», такие как быстрая сортировка и сортировка слиянием, превосходят сортировку вставками для больших массивов, нерекурсивные алгоритмы сортировки, такие как сортировка вставками или сортировка выбором, обычно быстрее для очень маленьких массивов (точный размер варьируется в зависимости от среды и реализации, но обычно составляет от 7 до 50 элементов). Поэтому полезной оптимизацией при реализации этих алгоритмов является гибридный подход, использующий более простой алгоритм, когда массив разделен до небольшого размера. Если стоимость сравнений превышает стоимость обменов, как это происходит, например, с ключами-строками, хранящимися по ссылке, или с взаимодействием с пользователем (например, при выборе одного из двух элементов, отображаемых рядом), то использование бинарной сортировки вставками может дать лучшую производительность. Бинарная сортировка вставками использует двоичный поиск для определения правильного положения для вставки новых элементов и, следовательно, выполняет ⌈log₂ n⌉ сравнений в худшем случае. Когда каждый элемент в массиве ищется и вставляется, это O(n log n). Чтобы избежать серии обменов при каждой вставке, входные данные можно хранить в связном списке, что позволяет вставлять или удалять элементы из списка за постоянное время, когда позиция в списке известна. Однако поиск в связном списке требует последовательного прохождения по ссылкам до нужной позиции: связный список не имеет произвольного доступа, поэтому он не может использовать более быстрый метод, такой как двоичный поиск. Следовательно, время, необходимое для поиска, составляет O(n), а время сортировки – O(n²). Если используется более сложная структура данных (например, куча или двоичное дерево), время, необходимое для поиска и вставки, можно значительно сократить; это суть сортировки кучей и сортировки двоичным деревом. В 2006 году Бендер, Мартин Фарач Колтон и Мостеиро опубликовали новый вариант сортировки вставками, называемый библиотечной сортировкой или сортировкой с пробелами, который оставляет небольшое количество неиспользуемых мест (то есть «пробелов») по всему массиву. Преимущество заключается в том, что вставки требуют сдвига элементов только до достижения пробела. Авторы показали, что этот алгоритм сортировки с высокой вероятностью выполняется за время O(n log n). Если используется пропускной список, время вставки сокращается до O(log n), и обмены не требуются, поскольку пропускной список реализован на основе структуры связного списка. Окончательное время выполнения для вставки составит O(n log n).

Insertion sort is very similar to selection sort. As in selection sort, after k passes through the array, the first k elements are in sorted order. However, the fundamental difference between the two algorithms is that insertion sort scans backwards from the current key, while selection sort scans forwards. This results in selection sort making the first k elements the k smallest elements of the unsorted input, while in insertion sort they are simply the first k elements of the input. The primary advantage of insertion sort over selection sort is that selection sort must always scan all remaining elements to find the absolute smallest element in the unsorted portion of the list, while insertion sort requires only a single comparison when the (k + 1) st element is greater than the k th element; when this is frequently true (such as if the input array is already sorted or partially sorted), insertion sort is distinctly more efficient compared to selection sort. On average (assuming the rank of the (k + 1) st element rank is random), insertion sort will require comparing and shifting half of the previous k elements, meaning that insertion sort will perform about half as many comparisons as selection sort on average. In the worst case for insertion sort (when the input array is reverse sorted), insertion sort performs just as many comparisons as selection sort. However, a disadvantage of insertion sort over selection sort is that it requires more writes due to the fact that, on each iteration, inserting the (k + 1) st element into the sorted portion of the array requires many element swaps to shift all of the following elements, while only a single swap is required for each iteration of selection sort. In general, insertion sort will write to the array O(n2) times, whereas selection sort will write only O(n) times. For this reason selection sort may be preferable in cases where writing to memory is significantly more expensive than reading, such as with EEPROM or flash memory. While some divide and conquer algorithms such as quicksort and mergesort outperform insertion sort for larger arrays, non recursive sorting algorithms such as insertion sort or selection sort are generally faster for very small arrays (the exact size varies by environment and implementation, but is typically between 7 and 50 elements). Therefore, a useful optimization in the implementation of those algorithms is a hybrid approach, using the simpler algorithm when the array has been divided to a small size. If the cost of comparisons exceeds the cost of swaps, as is the case for example with string keys stored by reference or with human interaction (such as choosing one of a pair displayed side by side), then using binary insertion sort may yield better performance. Binary insertion sort employs a binary search to determine the correct location to insert new elements, and therefore performs ⌈log2 n⌉ comparisons in the worst case. When each element in the array is searched for and inserted this is O(n log n). To avoid having to make a series of swaps for each insertion, the input could be stored in a linked list, which allows elements to be spliced into or out of the list in constant time when the position in the list is known. However, searching a linked list requires sequentially following the links to the desired position: a linked list does not have random access, so it cannot use a faster method such as binary search. Therefore, the running time required for searching is O(n), and the time for sorting is O(n2). If a more sophisticated data structure (e. g., heap or binary tree) is used, the time required for searching and insertion can be reduced significantly; this is the essence of heap sort and binary tree sort. In 2006 Bender, Martin Farach Colton, and Mosteiro published a new variant of insertion sort called library sort or gapped insertion sort that leaves a small number of unused spaces (i. e., "gaps") spread throughout the array. The benefit is that insertions need only shift elements over until a gap is reached. The authors show that this sorting algorithm runs with high probability in O(n log n) time. If a skip list is used, the insertion time is brought down to O(log n), and swaps are not needed because the skip list is implemented on a linked list structure. The final running time for insertion would be O(n log n).