Форма входа

Наша реклама

Помогите сайту просмотрите рекламу

Поиск

Календарь

«  Март 2024  »
ПнВтСрЧтПтСбВс
    123
45678910
11121314151617
18192021222324
25262728293031

Наш опрос

Оцените мой сайт
Всего ответов: 122

Статистика


Онлайн всего: 1
Гостей: 1
Пользователей: 0




Пятница, 29.03.2024, 08:35
Приветствую Вас Гость | RSS
Скорая помощь для студентов
Главная | Регистрация | Вход
Лекция 2


Реализация

Реализацию

 

// Коды для сортировки вставками

typedef int T;          /* Тип элемента, который нужно сортировать */

typedef int tblIndex;   /* Тип ключа сортировки */

 

#define compGT(a,b) (a > b)

 

void insertSort(T *a, tblIndex lb, tblIndex ub) {

    T t;

    tblIndex i, j;

 

   /**********************************

    *  Сортировка массива a[lb..ub]  *

    **********************************/

    for (i = lb + 1; i <= ub; i++) {

        t = a[i];

 

        /* Элементы сдвигаются вниз до */

        /* найденного места вставки.   */

        for (j = i-1; j >= lb && compGT(a[j], t); j--)

            a[j+1] = a[j];

 

        /* Вставка */

        a[j+1] = t;

    }

}

Дополнительно

Здесь рассмотрим более подробно группу простых методов сортировки. Кроме того в этом разделе мы будем рассматривать программы сортировок в нотации языка Pascal. Поэтому некоторые методы основного раздела могут здесь быть рассмотрены повторно. Итак…

Основное требование к методам сортировки массивов – экономное использование памяти. Это означает, что переупорядочение элементов нужно выполнять in situ (на том же месте) и что методы, которые пересылают элементы из массива A в массив B, пока не представляют для нас интереса. Таким образом, выбирая метод сортировки, классификацию алгоритмов удобно проводить в соответствии с их эффективностью, т.е. экономией времени или быстродействием. Удобная мера эффективности получается при подсчете числа С необходимых сравнений ключей и М пересылок элементов. Эти числа определяются некоторыми функциями от числа n сортируемых элементов.

Хотя хорошие алгоритмы сортировки требуют порядка (n*log(n))сравнений, мы сначала обсудим несколько несложных и очевидных способов сортировки, называемых простыми методами, которые требуют порядка n^2 сравнений ключей. Изучение простых методов важно по следующим причинам:

Методы, сортирующие in situ, можно разбить на три основных класса в зависимости от лежащего в их основе приема:

Теперь рассмотрим и сравним эти три принципа. Программы работают с массивом A, компоненты которой нужно рассортировать in situ,в этих программах используются типы данных item и index, определенные так:

                    type index = 0 .. n;

                    var A: array [1 .. n] of item;

 

Сортировка включениями

Сортировка включениями (то же, что вставками) есть общее название группы методов сортировки, основанных на последовательной вставке "новых” элементов в увеличивающийся упорядочиваемый список. Простейшим методом является линейная вставка.

 

Сортировка простыми включениями

Этот метод обычно используют игроки в карты. Элементы (карты) условно разделяются на готовую последовательность A[1],...,A[i-1] и входную последовательность A[i],...,A[n]. На каждом шаге, начиная с i=2 и увеличения i на единицу, берут первый элемент входной последовательности и передают в готовую последовательность, вставляя его на подходящее место.

Пример сортировки "просеивание”.

  начальные ключи 44 55 12 42 94 18 06 67

              i=2   44 55 12 42 94 18 06 67

              i=3   12 44 55 42 94 18 06 67

              i=4   12 42 44 55 94 18 06 67

              i=5   12 42 44 55 94 18 06 67

              i=6   12 18 42 44 55 94 06 67

              i=7   06 12 18 42 44 55 94 67

              i=8   06 12 18 42 44 55 67 94

Процесс сортировки включениями показан на примере восьми случайно взятых чисел. Алгоритм  сортировки  простыми включениями выглядит следующим образом:

      for i:= 2 to n do

       begin x:= A[i]

            "вставить х на подходящем месте в A[1]...A[i]"

       end

При поиске подходящего места чередовать сравнения и пересылки, т.е. как бы "просеивать" х, сравнивая его с очередным элементом A[j] и либо вставляя х, либо пересылая A[j] направо и продвигаясь налево. Заметим, что "просеивание" может закончиться при двух различных условиях:

Найти элемент A[j] с ключом меньшим, чем ключ х.

Достигнут левый конец готовой последовательности.

Этот типичный пример цикла с двумя условиями окончания дает нам возможность рассмотреть хорошо известный прием фиктивного элемента ("барьера"). Его можно легко применить в этом случае, установив барьер A[0] = х. (Заметим, что для этого нужно расширить диапазон индексов в описании A до 0,...,n). Окончательный алгоритм представлен ниже в виде программы.

Реализация

 procedure StraightInsertion;

  var i,j: index; x: item;

      begin

            for i:= 2 to n do

            begin x:= A[i]; A[0]:= x; j:= i-1

               while (x.key < A[j].key) do

                  begin A[j+1]:=A[j]; j:=j-1;

                  end;

               A[j+1]:=x;

            end;

      end;

 

Сортировка бинарными включениями

Алгоритм сортировки простыми включениями легко улучшить, если обратить внимание на то, что готовая последовательность A[1],...,A[i],в которую требуется включить новый элемент, уже упорядочена. Место включения можно найти значительно быстрее, если применить бинарный поиск. Модифицированный алгоритм сортировки называется сортировкой бинарными включениями, он приведен ниже в программе.

Реализация

       procedure BinaryInsertion;

       var i,j,l,r,m: index; x: item;

       begin

            for i:= 2 to n do

              begin x:=A[i]; l:=1; r:=i-1;

                while (l<=r) do

                  begin m:=(l+r) div 2;

                  if (x.key<A[m].key) then r:=m-1 else l:=m+1;

                  end;

                for j:=i-1 downto l do A[j+1]:=a[j];

                A[l]:=x;

            end;

      end;

 

Сортировка выбором

Линейный выбор

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

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

То, что адрес выбранного элемента находится в рабочей памяти, позволяет определять не только его место при пересылке, но и место, куда следует поместить фиктивный ключ. Если поле ключа является одновременно и полем элемента, то пересылка в список вывода может выполняться непосредственно из рабочей памяти, так как в ней находится вся запись. При каждом просмотре в список вывода добавляется текущий наименьший член сортируемого списка. Первый просмотр добавляет наименьший элемент, второй просмотр- следующий наименьший и т.д.. Таким образом, в области вывода формируется упорядоченный список. Сортировка заканчивается, когда все члены исходного списка окажутся в списке вывода.

 

Линейный выбор с обменом

Этот метод основан на следующем правиле:

Эти операции затем повторяются с оставшимися n-1 элементами, затем с n-2 элементами, пока не останется только один элемент - наибольший. Этот метод продемонстрирован на тех же восьми ключах:


 


             i=4   06 12 18 42 94 55 44 67 (42 уже на месте)


             i=6   06 12 18 42 44 55 94 67 (55 уже на месте)


             i=8   06 12 18 42 44 55 67 94

Программу можно представить следующим образом:

  for i:= 1 to n-1 do

   begin "присвоить k индекс наименьшего элемента из A[i] ...A[n]”

     "поменять местами A[i] и A[k]"

  end

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

Реализация

 procedure StraightSelection;

     var i,j,k: index; x: item;

      begin for i:= 1 to n-1 do

         begin  k:= i; x:= A[i];

           for j:= i+1 to n do

             if (A[j].key < x.key) then

             begin k:= j; x:= A[j];

             end;

           A[k]:= A[i]; A[i]:= x;

         end;

      end;

 



Copyright MyCorp © 2024