STL std :: sort () использует Introsort, но как это работает?

Question

Я действительно не понимаю алгоритм Introsort. Как вы можете видеть, я добавил псевдокод этого. Что подразумевается под maxdepth?

Что это значит "⌊log(length(A))⌋ × 2"

Я надеюсь, что кто-нибудь сможет мне это объяснить.

 procedure sort(A : array):
        let maxdepth = ⌊log(length(A))⌋ × 2
        introsort(A, maxdepth)

procedure introsort(A, maxdepth):
    n ← length(A)
    p ← partition(A)  // assume this function does pivot selection, p is the final position of the pivot
    if n ≤ 1:
        return  // base case
    else if maxdepth = 0:
        heapsort(A)
    else:
        introsort(A[0:p], maxdepth - 1)
        introsort(A[p+1:n], maxdepth - 1)

Answer 1

По вашему вопросу на ⌊log(length(A))⌋ × 2, бит ⌊...⌋ просто означает floor, наибольшее целое число, меньшее или равное значению.

На языке математического меньше, это будет int(log(length(A))) * 2.

---

И на всякий случай, если кто-то поднимает разницу между floor (округляется к -∞) и int (округляется к 0), этоздесь не имеет значения, поскольку длина должна быть неотрицательным целым числом.Вы по-прежнему будете сталкиваться с математическими проблемами, если длина равна нулю, но это исключительный случай, поскольку, вероятно, не требуется сортировка: -)

---

Что касается , почему maxdepthсуществует, это, очевидно, алгоритм, основанный на деревьях - использование log также поддерживает это, поскольку глубина сбалансированного дерева, как правило, пропорциональна логарифму числа узлов в нем.

Что кажетсядолжно случиться так, что, если интросорт выходит за пределы определенной глубины, он просто переключается на heapsort для остатка.

---

И, только одна небольшая нота: std::sort() это не требуется для использования Introsort (как видно из названия), стандартное поведение мандатов, такое как at most Nlog<sub>2</sub>N comparisons, where N=last-first, но в остальном не требует требований к выбору алгоритма.