Сортировка вставки с часовым

Question

Хотелось бы узнать, есть ли цель добавить часового в этот код?

public void Sort(ArrayToSort<T> array) {
    for (var i = 0; i < array.Length; i++) {
        for (var j = i; j > 0; j--) {
            if (array.isLess(j, j - 1)) {
                array.Swap(j, j - 1);
            } else {
                break;
            }
        }
    }
}

Если ответ положительный, как мне это сделать?Потому что, если я скопирую все вкладки, я уверен, что лучше обходиться без стража ... спасибо;)

Answer 1

Есть способ сделать натуральный дозорный в сортировке вставок.Сделайте первый обход по всему массиву, найдите самый маленький элемент и сдвиньте его в первую позицию.

После этого вы избавитесь от проверки индекса во внутреннем цикле.Пример кода для второго этапа из книги Седжвика (Alg. In C):

for (i = l+2; i <= r; i++)
  { int j = i; Item v = a[i];
    while (less(v, a[j-1]))
      { a[j] = a[j-1]; j--; }
    a[j] = v;
  }

Также обратите внимание, что сортировка вставки использует сдвиги элементов, а не свопы - для эффективности.

Использование этого метода вв худшем случае у вас будет n^2/2 сравнение элементов с (n^2/2 сравнение элементов + n^2/2 i ndex сравнений в тривиальном случае).

Я считаю, что увеличение скорости должно существовать, но оно не очень велико (сравнение элементов может быть более тяжелым, и в обоих случаях число операций сдвига также одинаково).Вы можете профилировать оба подхода и знать результат для вашего конкретного случая.