Почему сортировку вставками следует использовать после пересечения порогов в сортировке слиянием
Я читал везде, что для алгоритмов сортировки разделяй и властвуй, как Merge-Sort а также Quicksortвместо повторения до тех пор, пока не останется только один элемент, лучше перейти к Insertion-Sort когда достигается определенный порог, скажем, 30 элементов. Это хорошо, но почему только Insertion-Sort? Почему бы и нет Bubble-Sort или же Selection-Sortоба из которых имеют схожие O(N^2) спектакль? Insertion-Sort должен пригодиться только тогда, когда многие элементы предварительно отсортированы (хотя это преимущество должно Bubble-Sort), но в противном случае, почему он должен быть более эффективным, чем два других?
А во-вторых, по этой ссылке во 2-м ответе и сопутствующих комментариях говорится, что O(N log N) плохо работает по сравнению с O(N^2) до определенного N, Как так? N^2 всегда должен работать хуже, чем N log N, поскольку N > log N для всех N >= 2, верно?
6 ответов
- Сортировка вставок на практике быстрее, чем пузырьковая сортировка, по крайней мере. Их асимптотическое время выполнения такое же, но сортировка вставки имеет лучшие константы (меньше / дешевле операций за итерацию). В частности, он требует только линейного числа перестановок пар элементов, и в каждом внутреннем цикле он выполняет сравнение между каждым из n/ 2 элементов и "фиксированным" элементом, который может храниться в регистре (в то время как пузырьковая сортировка должна читать значения из памяти). Т.е. сортировка вставкой выполняет меньше операций во внутреннем цикле, чем сортировка пузырьком.
- Ответ утверждает, что 10000 n lg n > 10 n² для "разумного" n. Это верно примерно до 14000 элементов.
Если вы выходите из каждой ветви вашей быстрой сортировки "разделяй и властвуй", когда она достигает порогового значения, ваши данные выглядят так:
[the least 30-ish elements, not in order] [the next 30-ish ] ... [last 30-ish]
Сортировка вставки обладает довольно приятным свойством, что вы можете вызывать ее только один раз для всего этого массива, и она выполняет в основном то же самое, что и если вы вызываете ее один раз для каждого блока из 30. Поэтому вместо вызова этого в цикле у вас есть возможность называть это последним. Это может быть не так быстро, особенно если учесть, что все данные извлекаются из кеша в дополнительное время, но в зависимости от структуры кода это может быть удобно.
Ни пузырьковая сортировка, ни сортировка не обладают этим свойством, поэтому я думаю, что ответом может быть просто "удобство". Если кто-то подозревает, что сортировка может быть лучше, тогда бремя доказывания лежит на них, чтобы "доказать", что это быстрее.
Обратите внимание, что использование сортировки вставками также имеет недостаток - если вы сделаете это таким образом, и в вашем коде раздела есть ошибка, то при условии, что он не потеряет никаких элементов, просто разделите их неправильно, вы никогда не заметите.
Редактировать: по-видимому, эта модификация принадлежит Седжвику, который написал свою докторскую диссертацию по быстрой сортировке в 1975 году. Недавно она была проанализирована Массером (изобретателем Introsort). Ссылка https://en.wikipedia.org/wiki/Introsort
Муссер также рассмотрел влияние на кэши отложенной небольшой сортировки Седжвика, где небольшие диапазоны сортируются в конце за один проход сортировки вставкой. Он сообщил, что он может удвоить число пропусков кэша, но его производительность с двусторонними очередями была значительно выше и его следует сохранить для библиотек шаблонов, отчасти потому, что выигрыш в других случаях от немедленной сортировки был невелик.
В любом случае, я не думаю, что общий совет - "что бы вы ни делали, не используйте сортировку выбора". Совет заключается в том, что "сортировка вставок превосходит Quicksort для входных данных до удивительно не крошечного размера", и это довольно легко доказать самим себе, когда вы внедряете Quicksort. Если вы придумали другой вид, который явно превосходит сортировку вставок в тех же самых маленьких массивах, ни один из этих академических источников не скажет вам не использовать его. Я полагаю, что удивление заключается в том, что совет последовательно направлен на сортировку вставок, а не на каждый источник, выбирающий своего любимого (начинающие учителя испытывают откровенно удивительную любовь к пузырьковой сортировке - я не возражаю, если больше никогда не услышу об этом). Сортировка вставок обычно рассматривается как "правильный ответ" для небольших данных. Вопрос не в том, должен ли он быть "быстрым", а в том, действительно ли он есть или нет, и я никогда особо не замечал каких-либо критериев, рассеивающих эту идею.
Одним из мест для поиска таких данных было бы развитие и принятие Timsort. Я почти уверен, что Тим Питерс выбрал вставку по причине: он не предлагал общих советов, он оптимизировал библиотеку для реального использования.
Я удивлен, что никто не упомянул тот простой факт, что сортировка вставок просто намного быстрее для "почти" отсортированных данных. Вот почему он используется.
Вот эмпирическое доказательство, что сортировка вставкой выполняется быстрее, чем сортировка по пузырькам (для 30 элементов, на моей машине, присоединенная реализация, использующая Java...).
Я запустил прикрепленный код и обнаружил, что сортировка пузырьков выполнялась в среднем 6338,515 нс, а вставка заняла 3601,0
Я использовал тест со знаком Уилкоксона, чтобы проверить вероятность того, что это ошибка, и они на самом деле должны быть одинаковыми - но результат находится ниже диапазона числовой ошибки (и фактически P_VALUE ~= 0)
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int j = i;
while (j > 0 && arr[j-1] > arr[j]) {
swap(arr, j, j-1);
j--;
}
}
}
public static void bubbleSort(int[] arr) {
for (int i = 0 ; i < arr.length; i++) {
boolean bool = false;
for (int j = 0; j < arr.length - i ; j++) {
if (j + 1 < arr.length && arr[j] > arr[j+1]) {
bool = true;
swap(arr,j,j+1);
}
}
if (!bool) break;
}
}
public static void main(String... args) throws Exception {
Random r = new Random(1);
int SIZE = 30;
int N = 1000;
int[] arr = new int[SIZE];
int[] millisBubble = new int[N];
int[] millisInsertion = new int[N];
System.out.println("start");
//warm up:
for (int t = 0; t < 100; t++) {
insertionSort(arr);
}
for (int t = 0; t < N; t++) {
arr = generateRandom(r, SIZE);
int[] tempArr = Arrays.copyOf(arr, arr.length);
long start = System.nanoTime();
insertionSort(tempArr);
millisInsertion[t] = (int)(System.nanoTime()-start);
tempArr = Arrays.copyOf(arr, arr.length);
start = System.nanoTime();
bubbleSort(tempArr);
millisBubble[t] = (int)(System.nanoTime()-start);
}
int sum1 = 0;
for (int x : millisBubble) {
System.out.println(x);
sum1 += x;
}
System.out.println("end of bubble. AVG = " + ((double)sum1)/millisBubble.length);
int sum2 = 0;
for (int x : millisInsertion) {
System.out.println(x);
sum2 += x;
}
System.out.println("end of insertion. AVG = " + ((double)sum2)/millisInsertion.length);
System.out.println("bubble took " + ((double)sum1)/millisBubble.length + " while insertion took " + ((double)sum2)/millisBubble.length);
}
private static int[] generateRandom(Random r, int size) {
int[] arr = new int[size];
for (int i = 0 ; i < size; i++)
arr[i] = r.nextInt(size);
return arr;
}
РЕДАКТИРОВАТЬ:
(1) оптимизация пузырьковой сортировки (обновлено выше) сократила общее время, необходимое для пузырьковой сортировки, до: 6043.806, недостаточного для внесения существенных изменений. Тест Уилкоксона все еще убедителен: сортировка вставок выполняется быстрее.
(2) Я также добавил тест сортировки выбора (код прилагается) и сравнил его со вставкой. Результаты: выбор занял 4748,35, а вставка заняла 3540,114.
P_VALUE для Уилкоксона все еще находится ниже диапазона числовой ошибки (фактически ~ = 0)
Код для выбора сортировки используется:
public static void selectionSort(int[] arr) {
for (int i = 0; i < arr.length ; i++) {
int min = arr[i];
int minElm = i;
for (int j = i+1; j < arr.length ; j++) {
if (arr[j] < min) {
min = arr[j];
minElm = j;
}
}
swap(arr,i,minElm);
}
}
Сначала проще: зачем вставлять сортировку по выбору? Потому что сортировка вставкой в O(n) для оптимальных входных последовательностей, т.е. если последовательность уже отсортирована. Сортировка выбора всегда в O (n ^ 2).
Почему вставка сортируется по пузырьковой? Оба требуют только одного прохода для уже отсортированных входных последовательностей, но сортировка вставок ухудшается лучше. Чтобы быть более конкретным, сортировка вставкой обычно работает лучше с небольшим количеством инверсии, чем сортировка пузырьком. Источник Это может быть объяснено тем, что пузырьковая сортировка всегда проходит по элементам Ni на этапе i, в то время как сортировка вставкой работает больше как "находка", и ей нужно только перебрать (Ni)/2 элементов в среднем (на этапе Ni-1), чтобы найти вставку позиция. Таким образом, сортировка вставкой в среднем будет примерно в два раза быстрее, чем сортировка вставкой.
РЕДАКТИРОВАТЬ: Как указывает IVlad в комментарии, сортировка выбора делает только n перестановок (и, следовательно, только 3n записей) для любого набора данных, поэтому сортировка при вставке вряд ли превзойдет ее из-за меньшего количества перестановок - но, скорее всего, это будет существенно меньше сравнений. Приведенные ниже рассуждения лучше подходят для сравнения с пузырьковой сортировкой, которая проведет аналогичное количество сравнений, но в среднем будет гораздо больше свопов (и, следовательно, гораздо больше записей).
Одна из причин, по которой сортировка вставкой имеет тенденцию быть быстрее, чем другие алгоритмы O(n^2), такие как пузырьковая сортировка и сортировка выбора, заключается в том, что в последних алгоритмах каждое перемещение данных требует перестановки, которая может быть в 3 раза больше памяти копии, которые необходимы, если другой конец подкачки нужно будет поменять местами позже.
С сортировкой вставки OTOH, если следующий вставляемый элемент уже не самый большой элемент, он может быть сохранен во временном местоположении, и все нижние элементы шунтируются вперед, начиная справа и используя отдельные копии данных (т.е. без перестановок), Это открывает пробел, чтобы поместить оригинальный элемент.
C-код для вставки-сортировки целых чисел без использования перестановок:
void insertion_sort(int *v, int n) {
int i = 1;
while (i < n) {
int temp = v[i]; // Save the current element here
int j = i;
// Shunt everything forwards
while (j > 0 && v[j - 1] > temp) {
v[j] = v[j - 1]; // Look ma, no swaps! :)
--j;
}
v[j] = temp;
++i;
}
}