Структуры и алгоритмы обработки данных


Краткая теория - часть 3


Это предполагает, что перестановки, приводящие элементы в порядок, должны выполняться на том же месте, т.е. методы, в которых элементы из массива А передаются в результирующий массив H, представляют существенно меньший интерес. Ограничив критерием экономии памяти наш выбор нужного метода среди многих возможных, мы будем сначала классифицировать методы по их экономичности, т.е. по времени их работы. Хорошей мерой эффективности может быть С - число необходимых сравнений ключей и М - число пересылок (перестановок) элементов.

Эти числа - функции от n- числа сортируемых элементов. Хотя улучшенные алгоритмы сортировки требуют порядка n*log n сравнений, мы разберем простой метод, который причисляется к так называемым прямым, где требуется порядка n^2 сравнений ключей. К достоинствам прямых методов относятся :

1.Прямые методы особенно удобны для объяснения характерных черт основных  принципов большинства сортировок.

2.Программы этих методов легко понимать, и они коротки. Напомним, что сами программы также занимают память.

3.Улучшенные методы требуют небольшого числа операций, но эти операции обычно сами более сложны, и поэтому для достаточно малых n прямые методы оказываются быстрее, хотя при больших n их использовать, конечно, не следует.

   Методы сортировки "на том же месте" можно разбить в соответствии с определяющими их принципами на три основные категории:

1.Сортировки прямым включением Bу insertion .

2.Сортировки прямым выделением Bу selection .

3.Сортировки прямым обменом Bу exchange .

 




- Начало -  - Назад -  - Вперед -



Книжный магазин