Прямой и двоичный вид вставки

Question

Прямой и двоичный вид вставки

Здравствуйте, меня попросили улучшить сортировку вставок, используя бинарный поиск вместо линейного. Проблема состоит в том, что лучший случай теперь O (n log n) вместо O (n) из-за сравнение данных, что сделало программу, если не медленнее, в некоторых случаях равной. Вот мой двоичный код сортировки вставки:

void InsertionSort(int data[], int size)
{
int index = -1;
for(int i = 1,temp,j;i<size;i++)
{
temp = data[i];//DM O(N)
int high = i,low = 0,mid;//DM O(N)
while(low <= high)//DC O(nlogn)
{
mid = (low + high) /2;
if(temp < data[mid])
{
high = mid - 1;
index = mid;
}

else if (temp > data[mid])
{
low = mid + 1;
}

else if(data[mid] == temp)
{
index = mid;
break;
}

}
for(j = i;j > index;j--)
{
data[j] = data[j-1];//DC Worst Case O(n*n) but the exact is summation of n(n+1) / 2 nad best case o(1)
}
data[j] = temp;//DM O(n)
}
}

0

binary-search c++data-structures sorting

Решение

Другие решения

Вы также можете заменить последнее:else if(data[mid] == temp) с простым else
потому что очевидно, что это правда, если первые два не были правдой …

-1

Источник

Accepted Answer

Вы можете начать бинарный поиск с предвзятой стадии, которая благоприятствует лучшему случаю. Вместо того, чтобы идти прямо к (low+high)/2, начать с позиции i-1, затем i-2, затем i-4, i-8, i-16, i-32… пока вы не найдете меньший элемент, или пока i-whatever становится ниже, чем low, Затем продолжите обычный бинарный поиск.

Обратите внимание, что эта оптимизация обходится дорого. В лучшем случае — отсортированные или почти отсортированные данные — требуется время O (N), но средний и худший случай становятся немного медленнее по сравнению с простой версией двоичного поиска.

void InsertionSort (int data[], int size)
{
int i, j, high, low, mid, hop;
int temp;

for (i=1; i<size; i++)
{
temp = data[i];

high = i;
low = 0;
hop = 1;

do
{
mid = high - hop;
hop <<= 1;

if (temp < data[mid])
high = mid;
else
low = mid + 1;
}
while (low+hop <= high);

while (low != high)
{
mid = (low + high) / 2;

if (temp < data[mid])
high = mid;
else
low = mid + 1;
}

for(j=i; j>low; j--)
data[j] = data[j-1];

data[j] = temp;
}
}

Обратите внимание, что high назначен mid и не mid+1, Случай, когда temp==data[mid] трактуется как случай, когда temp>data[mid], Это нужно для сохранения хорошего свойства сортировки вставки: это стабильный сорт. Это не имеет значения при сортировке простых целых чисел.

0