Сортировка

Материал из Викиконспекты
Перейти к: навигация, поиск

Сортировкой называется процесс упорядочивания множества объектов по какому-либо признаку.

Обычно таким признаком служит лексикографический номер.

Классификация сортировок

Будем рассматиривать сортировки массива из [math]n[/math] элеметов из множества [math]А[/math], причем на [math]А[/math] должно быть выполнено отношение эквивалентности.

  • Время работы.

Эта классификация является самой важной. В основном временные оценки бывают <wikitex>$O(n)$, $O(n \log n)$ и $O(n^2)$</wikitex>