Как изменить обычную сортировку вставками так, чтобы алгоритм использовал бинарный поиск?

Question

[netrox]

Обычный алгоритм вставки:

for(int i=1;i<n;i++)
{
    temp=array[i];
    index=i;
    while(index>0 && array[index-1]>=temp)
    {
        array[index]=array[index-1];
        index--;
    }
    array[index]=array[i];
}

Answer 1

[Wataru]

Бесполезно прикручивать к сортировке вставками бинарный поиск. Кроме поиска места, куда вставляется новый элемент - надо еще и этот элемент вставить. При этом массиве придется сдвигать O(n) элементов при каждой вставке. В связном списке не пришлось бы сдвигать элементы, но там невозможно сделать бинарный поиск, потому что нет быстрого произвольного посика.

Приведенная вами реализация - довольно быстрая. Тут поиск места вставки и сдвиги всех элементов объединены. Теоретически, можно сначала сделать бинарный поиск и вместо цикла while использовать, допустим, цикл for с фиксированным количеством итераций. Это сократит количество сравнений в цикле 2 раза, но добавит сколько-то сравнений и нелокальных обращений к памяти в бин.поиске. Возможно будет работать быстрее только если входные данные почти в обратном порядке заданы. В среднем же, будет работать хуже.

Гораздо лучшая реализация была бы изначально зарезервировать первый элемент в массиве и записать туда очень маленькое число. А сами данные записывать после него. Тогда в цикле while не надо будет сравнивать index>0. Эта реализация будет гораздо быстрее дополнительного бинарного поиска.

Comments

[netrox]

Да, бинарный поиск не лучшая затея , но лектор любитель паскаля требует этот метод

[Wataru]

Тогда в начале в цикле for найдите бинпоиском в массиве в позициях 0..i-1 наибольший элемент, меньший array[i]. Пусть эта позиция j. Потом, все там же внутри цикла for циклом while (почти как сейчас) сдвиньте все элементы правее j на одну позицию вправо. Т.е. цикл будет while (index > j+1). Дальше все остается точно так же и внутри цикла while и после. Важно, чтобы ваша реализация бинарного поиска возвращала -1, если все элементы array[0..i-1] больше равны array[i]. Как будто-бы в -1 позиции в массиве стоит бесконечно маленькое число.