| Цитата |
Метод простых вставок
В обычной жизни мы сталкиваемся с этим методом при игре в карты. Чтобы отсортировать имеющиеся в Вас карты, Вы вынимаете карту, сдвигаете оставшиеся карты, а затем вставляете карту на нужное место. Процесс повторяется до тех пор, пока хоть одна карта находится не на месте.
Метод основывается на следующем: считается, что перед рассмотрением записи R[j] предыдущие записи R[1], R[2], ..., R[j-1] уже упорядочены, и R[j] вставляется в соответствующее место.
Сортировка таблицы начинается со второй записи. Ее ключ сравнивается с ключом первой записи, и, если упорядоченность нарушена, то записи R[1] и R[2] переставляются. Затем ключ записи R[3] сравнивается с ключами записей R[2] и R[1]. На j-м шаге К[j] сравнивается по очереди с K[j-1], K[j-2], ... ( K[1]<=K[2]<=...<=K[j-1] ) до тех пор, пока выполняется условие K[j] < K[i] ( i = j-1, j-2, ... ) или достигнут левый конец упорядоченной подтаблицы ( i = 1, K[j] < K[1] ). Выполнение условия K[j] >= K[i] означает, что запись R[j] нужно вставить между R[i] и R[i+1]. Тогда записи R[i+1], R[i+2], ..., R[j-1] сдвигаются на одну позицию, и запись R[j] помещается в позицию i+1.
Операции сравнения и перемещения записей удобно совмещать, перемежая их друг с другом (этот способ называется "просеиванием").
| Код |
/* array - сортируемая таблица (массив) */
/* size - количество эллементов */
void sort( int *array, int size )
{
register int i, j;
int temp;
for( i = 1; i < size; i++ )
{
temp = array[i];
for ( j = i - 1; j >= 0; j--)
{
if( array[j] < temp )
break;
array[j+1] = array[j];
}
array[j+1] = temp;
}
}
|
Количество операций сравнения для данного метода вставки равно N(N-1)/4. Максимальное количество перестановок при использовании этого метода примерно равно (N*N)/4.
Метод вставки обычно используется тогда, когда записи вносятся в упорядоченную таблицу. Новая запись должна быть вставлена в таблицу таким образом, чтобы существующая упорядоченность не нарушалась. Этот метод эффективен когда записи часично упорядочены, т.е. записи находятся не далеко от своих конечных положений.
Метод бинарного включения (бинарные вставки)
Этот метод упоминается Джоном Мочли в 1646г. в первой публикации по машинной сортировке.
Данный метод является улучшенной версией предыдущего метода простых вставок. Он основывается на том факте, что мы вначале ищем место куда нужно вставить элемент, а затем уже вставляем. Это дает существенный выигрыш по числу сравнений, но число перестановок по прежнему остается большим.
Поскольку все методы массива перед записью R[j] уже упорядочены, то можно использовать более эффективный метод поиска места куда надо вставить R[j]. В данном случае это алгоритм бинарного поиска. Например, если вставляется 64-я запись, то можно сравнить ее с 32-й, и если 64-я запись окажется меньше, то сравнить ее уже с 16-й, а если окажется больше, то сравнить с 48-й и т.д. Таким образом, место 64-й записи будет определено в худшем случае за шесть сравнений.
Общее число сравнений равно приблизительно N*logN, число перестановок попржнему остается квадратичнозависимым от N.
Метод двухпутевых вставок
Существует несколько методов для уменьшения числа перемещений в описанном методе вставок. Один из них - метод двухпутевых вставок, разработанный в начале 50-х годов.
Первый элемент помещается в середину области вывода, и место для последующих выводов освобождается сдвигом влево или вправо, туда куда удобней. Таким образом удается сэкономить примерно половину времени по сравнению с простыми вставками за счет некоторого усложнения алгоритма. Число перестановок сократится примерно в 2 раза до N*N/8.
|
|