Программы •Железо • Драйверы • Хостинг •Энциклопедия рекламы

     Метод "Пузырька"

При использовании этого способа требуется самое большее (n-1) проходов. В течение первого прохода таблицы сравниваются ключи К1 и К2 первой и второй записей, и, если порядок между ними нарушен,    то записи R1 и R2 меняются местами. Затем этот процесс повторяется для записей R2 и R3, R3 и R4 и т.д. Данный метод заставляет двигаться, или "всплывать", записи с малыми ключами.    Поспервого прохода запись с наибольшим    ключом будет находиться на n - й позиции таблицы. При каждом последующем проходе записи со следующем наибольшим ключом будут располагаться в позициях n-1,    n-2, ... , 2 соответственно, в
результате чего будет сформирована отсортированная таблица. После каждого прохода через таблицу может быть сделана проверка, были ли совершены перестановки в течение данного прохода. Если перестановок не было, то это означает, что таблица уже отсортирована и дальнейших проходов не требуется. Кроме того,можно запоминать индекс последней перестановки. Это позволит уменьшить на следующем шаге просматриваемую подтаблицу.
Характеристики сортировки методом "пузырька" в худшем случае составляют n(n-1)/2 сравнений и n(n-1)/2 перестановок (худшим считается случай,когда элементы наиболее удалены от своих конечных позиций).
Среднее число сравнений и перестановок имеет порядок n**2 .

Процедура, реализующая метод "пузырька" на языках Паскаль и Си, приведена ниже.

Type                                                     ¦ typedef
Rec=Record                                         ¦ struct{
    f1 : char;                                           ¦     char f1;
    f2 : integer;                                        ¦     int f2;
    f3 : integer                                         ¦     int f3; } rec;
End;          
Table = Array[1..100] Of Rec;              ¦ rec[100]     table;
procedure bubble(var T:Table;               ¦ void bubble(table *t,int n);
        n:integer);                                       ¦ /* t - таблица */
{ T - таблица; n - ее размер }             ¦ /* n - количество записей */
{ сортировка по полю f3}                  ¦ /* сортировка по полю f3 */
                                                             ¦ {
var                                                         ¦ int i,j,pr;
i:integer;                                                 ¦ rec el;
temp:Rec;                                              ¦ /* сортировка по полю f3 */
switch:boolean;                                      ¦ do{
begin                                                     ¦ pr=0;
repeat                                                    ¦ for( j=0;j<n;j++)
switch:=false;                                         ¦ {
for i:=1 to n-1 do                                   ¦     if(*t[j].f3>*t[j+1].f3)
if T[i].f3>T[i+1].f3 then                          ¦     {
begin                                                     ¦     el=*t[j];
switch:=true;                                          ¦     *t[j]=*t[j+1];
temp:=T[i];                                            ¦     *t[j+1] = el;
T[i]:=T[i+1];                                          ¦     pr=1;
T[i+1]:=temp                                         ¦     }
end                                                        ¦ }
until not(switch)                                      ¦ }while(pr==1);
end                                                        ¦ }

    Сортировка пузурьковым методом.

    Сортировка пузырьковым методом использует метод обменной  сортировки. Она основана на выполнении в цикле операций сравнения   и при необходимости обмена соседних элементов. Ее название происходит из-за подобия процессу движения пузырьков в резервуаре с  водой, когда каждый пузырек находит свой собственный уровень. Ниже показана самая простая форма программы сортировки методом пу зырька:
  { сортировка пузырьковым методом}
        procedure Bubble(var item: DataArray; count:integer);
        var
        i,j: integer;
        x: DataItem;
        begin
        for i := 2 to count do
        begin
        for j := count downto i do
        if item[j-1]>item[j] then
        begin
            x := item[j-1];
            item[j-1] := item[j];
            item[j] := x;
        end;
        end;
        end; {конец сортировки пузырьковым методом}

    В этом случае данное "item" является массивом элементов  "DataItem", который сортируется, а данное "count" содержит число элементов в массиве.  Сортировка пузырьковым методом имеет два цикла. Поскольку  число элементов массива задается переменной "count", внешний цикл  вызывает просмотр массива count - 1 раз. Это обеспечивает нахождение каждого элемента в своей позиций после завершения процедуры. Внутренний цикл предназначен для фактического выполнения операций сравнения и обмена. Эта версия сортировки пузырьковым методом может сортировать  символьный массив в порядке возрастания значений элементов. Нап ример, следующая короткая программа сортирует строку, которая  считывается с дискового файла "test.dat". Эта же программа может   использоваться с другими подпрограммами сортировки, которые при водятся в этой главе.

    program SortDriver;

    {эта программа будет считывать 80 или меньше символов с
    дискового файла "test.dat", отсортирует их и выдаст
    pезультат на экран дисплея }

    type
        DataItem = char;
        DataArray = array [1..80] of char;
    var
        test: DataArray;
        t, t2: integer;
        testfile: file of char;
    { сортировка пузырьковым методом}
    procedure Bubble(var item: DataArray; count:integer);
    var
        i,j: integer;
        x: DataItem;
    begin
        for i := 2 to count do
        begin
        for j := count downto i do
        if item[j-1]>item[j] then
        begin
        x := item[j-1];
        item[j-1] := item[j];
        item[j] := x;
        end;
        end;
    end;
    begin
        Assign(testfile, 'test.dat');
        Reset(testfile);
        t := 1;

    { считывание символов,которые будут сортироваться.}

    while not Eof(testfile) do begin
        read(testfile, test[t]);
        t := t+1;
        end;
    t := t-2; {скорректировать число считанных элементов }

    Bubble(test, t); { сортировать массив }

    { выдать отсортированный массив символов }
    for t2 := 1 to t do write(test[t2]);
    WriteLn;
    end.

    Сортировку пузырьковым методом можно в    некоторой степени   улучшить и тем самым немного улучшить ее временные характеристи ки. Можно, например, заметить, что сортировка пузырьковым методом    обладает одной особенностью: расположенный не на своем месте в  конце массива элемент (например, элемент "а" в массиве "dcab")  достигает своего места за один проход, а элемент, расположенный в начале массива (например, элемент "d"), очень медленно достигает своего места.     Необязательно все просмотры делать в одном направлении. Вместо этого всякий последующий просмотр можно делать в противоположном направлении.    В этом случае сильно удаленные от своего места элементы будут быстро перемещаться в соответствующее место. Ниже показана улучшенная версия сортировки пузырьковым методом, получившая название "челночной сортировки" из-за соот ветствующего характера движений по массиву.   Хотя эта сортировка является улучшением пузырьковым методом,  ее нельзя рекомендовать для использования, поскольку время выполнения по-прежнему зависит квадратично от числа элементов. Число сравнений не изменяется, а число обменов уменьшается лишь на незначительную величину.
    { челночная сортировка является улучшенной версией сортировки пузырьковым методом }

        procedure Shaker(var item: DataArray; count:integer);
        var
        j, k, l, r: integer;
        x: DataItem;
        begin
        l := 2; r := count; k := count;
        repeat
        for j := r downto l do
        if item[j-1] then
        begin { обмен }
            x := item[j-1];
            item[j-1] := item[j];
            item[j] := x;
            k := j;
        end;

        l := k+1;

        for j := l to r do
        if item[j-1]>item[j] then
        begin { обмен }
            x := item[j-1];
            item[j-1] := item[j];
            item[j] := x;
            k := j;
        end;

        r := k-1;
        until l>r
    end; { конец челночной сортировки }

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