Лекция. Алгоритмы сортировки Под сортировкой
Анализ сортировки двоичными вставками
жүктеу/скачать 0,94 Mb.
|
- Бұл бет үшін навигация:
- Простая сортировка выбором
- Анализ простой сортировки выбором
| Анализ сортировки двоичными вставками. Позиция вставки найдена, если L=R. Поэтому интервал поиска должен в итоге иметь длину 1; для этого нужно делить интервал длины i пополам log(i) раз.
Число сравнений примерно равно C ≈ n*(log(n) – log(e) ± 0.5). Простая сортировка выбором Данный метод основан на следующей схеме: 1. Выберем элемент с наименьшим ключом. 2. Переставим его с первым элементом a0. 3. Повторим эти операции с остальными n–1 элементами, затем с n–2 элементами.., пока не останется только один – наибольший – элемент. Проиллюстрируем метод на той же последовательности из восьми ключей, что и в табл. 2.1: Алгоритм формулируется следующим образом: for (i= 0; i<=n–1;i++) { присвоить k индекс наименьшего элемента из ai ... an–1; переставить ai и ak } Этот метод можно назвать простой сортировкой выбором. В некотором смысле он противоположен простой сортировке вставками: в последней на каждом шаге, чтобы найти позицию вставки, рассматривается один очередной элемент массива-источника и все элементы массива-приемника; в простой сортировке выбором просматривается весь массив-источник, чтобы найти один элемент с наименьшим ключом, который должен быть вставлен в массив-приемник. // StraightSelection int i, j, k, x; for (i = 0; i<= n–2; i++) { k := i; x := a[i]; for (j = i+1; j<= n–1; j++) { if (a[j] < x) { k = j; x = a[k] } } a[k] = a[i]; a[i] = x; } Анализ простой сортировки выбором. Очевидно, число C сравнений ключей не зависит от начального порядка ключей. В этом смысле можно сказать, что этот метод ведет себя не так естественно, как метод простых вставок. Получаем: C = (n2–n)/2 Число M пересылок не меньше, чем Mmin = 3*(n–1) для изначально упорядоченных ключей, и не больше, чем Mmax = n2/4+3*(n–1), если изначально ключи стояли в обратном порядке. жүктеу/скачать 0,94 Mb. Достарыңызбен бөлісу:
|