Сортировка вставками — хороший выбор для небольших наборов данных. Что маленькое?

Я видел много мест, где говорится о том, как сортировка вставками хороша для небольших наборов данных. Я не могу найти число для того, что "маленький", хотя. Я предполагаю, что нет абсолютного ответа и что он зависит от типа машины, на которой выполняется код.

Однако какие факторы влияют на принятие решения о пороговом значении, когда сортировка вставками является хорошей идеей? И какие примерные цифры для "маленьких"? 5? 10? 50? 100?

Спасибо!

Сайт говорит, что сортировка вставками подходит для небольших наборов данных: https://www.toptal.com/developers/sorting-algorithms/insertion-sort


sorting algorithm insertion-sort
person Don Quixote    schedule 16.12.2018    source источник
comment
Каково ваше определение небольшой суммы денег? Маленький означает достаточно маленький в ваших обстоятельствах. Вы должны протестировать ваше оборудование с вашими данными и найти пороговый размер, который подходит вам. При этом реализация GNU qsort определяет его как 4, см. stackoverflow.com/questions/19123683/   -  person n. 1.8e9-where's-my-share m.    schedule 16.12.2018
comment
Спасибо. Это значительно меньше, чем я всегда предполагал, что было ~ 30.   -  person Don Quixote    schedule 16.12.2018
comment
Я тоже всегда предполагал что-то около 30, я думаю, что видел это в какой-то реализации qsort, но потом я погуглил комментарий выше и нашел 4...   -  person n. 1.8e9-where's-my-share m.    schedule 16.12.2018
comment
Библиотека шаблонов Microsoft (алгоритм) использует 32 как для std::sort, так и для std::stable_sort.   -  person rcgldr    schedule 17.12.2018
comment
@н.м. но этот код используется только в том случае, если набор данных слишком велик для сортировки слиянием (для чего требуется выделение памяти).   -  person rici    schedule 17.12.2018

Ответы (2)


arrow_upward
1
arrow_downward

Да, ваша догадка верна - абсолютного ответа нет, нужно измерить, где находится порог между сортировкой вставками и другими методами.

Например, типичные значения для запуска сортировки вставками (и получения некоторого выигрыша, конечно) для небольших фрагментов внутри комбинированного слияния или быстрой сортировки составляют около 32-100 (но могут варьироваться в зависимости от данных и деталей реализации).

person MBo    schedule 16.12.2018

arrow_upward
1
arrow_downward

Попытка ответа, если мы говорим об общей проблеме сортировки. Сортировка вставками в среднем O (n ^ 2), эффективные алгоритмы сортировки в среднем O (nlogn). Таким образом, смутно говоря, если что-то требует K шагов для эффективной сортировки, это займет около (вроде) K ^ 2 шагов с сортировкой вставками.

Таким образом, если n > K слишком медленно для вас с эффективной сортировкой, n > K ^ 0,5 будет слишком медленным для вас (примерно) с сортировкой вставками.

С практической точки зрения, скажем, вы довольны сортировкой массивов размером 10 ^ 8 с помощью чего-то эффективного, тогда вы можете быть счастливы отсортировать массивы размера 10 ^ 4 с помощью сортировки вставками.

person Countingstuff    schedule 16.12.2018