Лекция. Алгоритмы сортировки Под сортировкой
Простая сортировка вставками
жүктеу/скачать 0,94 Mb.
|
- Бұл бет үшін навигация:
- Анализ простой сортировки вставками
| Простая сортировка вставками
Этот метод часто используется игроками в карты. Элементы (карты) мысленно разделяются на последовательность-приемник a0 ... ai–1 и последовательность- источник ai ... an–1. На каждом шаге, начиная с i=1 и затем увеличивая i на единицу, в последовательности-источнике берется i-й элемент и ставится в правильную позицию в последовательности-приемнике. В табл. 2.1 работа сортировки вставками показана на примере восьми взятых наугад чисел. Алгоритм простых вставок имеет вид for (i = 1;i<= n–1;i++) { x = a[i]; вставить х в правильную позицию среди a0 ... ai–1 } При поиске правильной позиции для элемента удобно чередовать сравнения и пересылки, то есть позволять значению x «просеиваться» вниз, при этом сравниваем x со следующим элементом aj, а затем либо вставляем x, либо передвигаем aj вправо и переходим влево. Заметим, что есть два разных условия, которые могут вызвать прекращение процесса просеивания: 1. У элемента aj ключ оказался меньше, чем ключ x. 2. Обнаружен левый конец последовательности-приемника. // StraightInsertion int i, j, x; for (i= 1; i<=n–1;i++) { x= a[i]; j = i; while ((j > 0) & (x < a[j–1])) { a[j] := a[j–1]; j++; } a[j]= x; } Анализ простой сортировки вставками. Число сравнений ключей в i-м просеивании Ci не больше i–1, как минимум равно 1 и – предполагая, что все перестановки n ключей равновероятны, – в среднем равно i/2. Число Mi пересылок (присваиваний элементов) равно Ci+1. Поэтому полные числа сравнений и пересылок равны Cmin = n–1 Mmin = 2*(n–1) Cave = (n2–n)/4 Mave = (n2+3n–4)/4 Cmax = (n2–3n+2)/2 Mmax = (n2–n)/2 Этот алгоритм нетрудно усовершенствовать, заметив, что последовательность-приемник a0 ... ai–1, в которую нужно вставить новый элемент, уже упорядочена. Поэтому можно использовать более быстрый способ нахождения позиции вставки. Очевидный выбор – алгоритм деления пополам, в котором проверяется середина последовательности-приемника и затем продолжаются деления пополам, пока не будет найдена точка вставки. Такой модифицированный алгоритм называется сортировкой двоичными вставками: // BinaryInsertion; int i, j, m, L, R, x; for (i = 1; i<= n–1; i++) { x = a[i]; L = 0; R = i; while (L < R) { m = (L+R) div 2; if (a[m] <= x) L = m+1; else R = m; } for (j = i; j>= R+1; j--) a[j] = a[j–1]; a[R] = x; } жүктеу/скачать 0,94 Mb. Достарыңызбен бөлісу:
|