VPF::Алгоритмы сортировки - Форум программистов

this

Дата 9.4.2006, 23:22 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 98
Регистрация: 12.9.2005

Репутация: нет
Всего: 1

Народ, срочно нужен алгоритм сортировки двухпутевыми вставками. Поиск что-то ничего толкового не дал.

Akina

Дата 10.4.2006, 08:55 (ссылка)

(нет голосов)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454

Цитата

Метод простых вставок
В обычной жизни мы сталкиваемся с этим методом при игре в карты. Чтобы отсортировать имеющиеся в Вас карты, Вы вынимаете карту, сдвигаете оставшиеся карты, а затем вставляете карту на нужное место. Процесс повторяется до тех пор, пока хоть одна карта находится не на месте.

Метод основывается на следующем: считается, что перед рассмотрением записи 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.

--------------------

О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

FaXeL

Дата 10.4.2006, 22:49 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 2
Регистрация: 10.4.2006

Репутация: нет
Всего: нет

Может подскажете и алгоритм сортировки "кучей"?

cercesaflaster

Дата 18.4.2006, 00:10 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 1
Регистрация: 18.4.2006

Репутация: нет
Всего: нет

здесь посмотри: http://www.codelab.ru/cat/3/
может есть то что ты ищешь

Akina

Дата 18.4.2006, 11:59 (ссылка)

(нет голосов)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454

Может, Вы начнете пользоваться поиском aka STFW?

--------------------

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »