Сортировка — различия между версиями
Yurik (обсуждение | вклад) |
Yurik (обсуждение | вклад) |
||
| Строка 5: | Строка 5: | ||
== Классификация сортировок == | == Классификация сортировок == | ||
| − | Будем рассматиривать сортировки массива из <tex>n</tex> элеметов из множества <tex>А</tex>, причем на <tex>А</tex> должно быть выполнено отношение эквивалентности. | + | Будем рассматиривать сортировки массива из <tex>n</tex> элеметов из множества <tex>А</tex>, |
| + | причем на <tex>А</tex> должно быть выполнено [[Бинарное отношение|отношение эквивалентности]]. | ||
| + | * Время работы. | ||
| − | + | Эта классификация является самой важной. В основном временные оценки бывают <wikitex>$O(n)$, $O(n \log n)$ и $O(n^2)$</wikitex> | |
[[Категория: Дискретная математика и алгоритмы]] | [[Категория: Дискретная математика и алгоритмы]] | ||
[[Категория: Сортировки]] | [[Категория: Сортировки]] | ||
Версия 22:45, 11 июня 2012
Сортировкой называется процесс упорядочивания множества объектов по какому-либо признаку.
Обычно таким признаком служит лексикографический номер.
Классификация сортировок
Будем рассматиривать сортировки массива из элеметов из множества , причем на должно быть выполнено отношение эквивалентности.
- Время работы.
Эта классификация является самой важной. В основном временные оценки бывают <wikitex>$O(n)$, $O(n \log n)$ и $O(n^2)$</wikitex>
