IntroSort

Алгоритмы   24 Март 2012  Автор статьи:  

Во многих языках программирования часто используется сортировка, называемая IntroSort, которая представляет собой модификацию быстрой сортировки(qsort). эта модификация гарантирует время работы не более O(nlog(n)) на любых данных и при этом в среднем работает как qsort(то есть быстрее, чем , например, heap sort).
Принципы работы алгоритма intro sort:

  • Если количество элементов крайне мало (n<7), то производится разбор случаев с помощью операций ветвления и обменов, делающих минимальное количество действий
  • В другом случае запускается qsort
  • Если очередной вызов qsort работает на слишком большой глубине, то на этом уровне массива запускается heapsort

Научиться программировать

  • на Delphi

  • на Java

  • на C++