78180

Разработка программ с использованием методов сортировки

Лабораторная работа

Информатика, кибернетика и программирование

Изучить основные приемы программирования по написанию программ с использованием сортировок включением, выбором и обменных сортировок. Согласно своему варианту разработать программу с применением одного из методов сортировки массивов.

Русский

2015-02-07

77 KB

5 чел.

Тема: Разработка программ с использованием методов сортировки

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

Время выполнения: 2 часа.

Лабораторная работа № 11

Порядок выполнения работы:

  1.  Изучить основные приемы программирования по написанию программ с использованием сортировок включением, выбором и обменных сортировок.
  2.  Согласно своему варианту разработать программу с  применением одного из методов сортировки массивов.
  3.  Показать работающую программу преподавателю. Уметь ответить на вопросы.
  4.  Получить у преподавателя индивидуальное задание в качестве домашнего упражнения. Самостоятельно разработать алгоритм решения задачи, составить и отладить программу.

Теоретические сведения

Существует три группы методов внутренней сортировки (сортировка включением, сортировка выбором, обменная сортировка).

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

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

На каждом проходе происходит перемещение i-того элемента в готовую последовательность, а некоторое число элементов сдвигается вправо. Данный процесс перемещения называется просачиванием элемента.

Здесь и далее, во всех процедурах сортировки ключи упорядочиваются по возрастанию. На входе процедур - количество элементов массива (n), на выходе - упорядоченный массив элементов(а).

Procedure Straight_Insertion(n:integer; Var a:array of integer);

Var  i,j:word;

x:integer;

Begin

    For i:=2 To n Do

    begin

x:=a[i]; a[0]:=x; j:=i-1;

       While x<a[j] Do

           begin

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

           end;

                    a[j+1]:=x

     end;

End;{Straight_Insertion}

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

Procedure Binary_Insertion(n:word;Var a: array[-400..1000] of integer);

Var

i,j,l,r,m:word;

x:integer;

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<a[m] 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;{Binary_Insertion}

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

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

{ Поиск в массиве методом перебора элементов }

program poisk;

const size = 10;

var

    massiv:array[1..size] of integer; { массив целых}

    obrazec:integer; { образец для поиска }

    naiden:boolean; { признак совпадения с образцом }

    i:integer;

begin

    { ввод 10 целых чисел }

    writeln('Поиск в массиве.');

    write('Введите ',size:3, ' целых в одной строке через пробел ');

    writeln ('и нажмите <Enter>');

    write('->');

    for i:=1 to size do read(massiv[i]);

    { числа введены в массив }

    write('Введите образец для поиска (целое число)-> ');

    readln(obrazec);

    { поиск простым перебором }

    naiden:=FALSE; { совпадений нет }

    i:=1; { проверяем с первого элемента массива }

    repeat

         if massiv[i] = obrazec

              then naiden:=TRUE     { совпадение с образцом }

              else i:=i+1;     { переход к следующему элементу }

    until (i>10) or (naiden); { завершим, если совпадение  с образцом или проверен }

              { последний элемент массива }

    if naiden   then writeln('Совпадение с элементом номер', i:3,'. ') {writeln('Поиск успешен.')}

         else writeln('Совпадений с образцом нет.');

end.

Существует три группы методов внутренней сортировки (сортировка включением, сортировка выбором, обменная сортировка). В данной лабораторной работе рассмотрены методы обменных сортировок.

Сортировка прямого обмена (пузырьковая)

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

Начнем последовательность обменов с элементами а[N]. В каждом проходе местами меняются соседние элементы. Самый легкий элемент поднимается за один проход, самый тяжелый опускается вниз за один проход. Если самый большой элемент был первым, то выполняется N проходов. Критерием окончания является отсутствие обменов при очередном проходе.

Здесь и далее, во всех процедурах сортировки ключи упорядочиваются по возрастанию. На входе процедур - количество элементов массива (n), на выходе - упорядоченный массив элементов(а).

Program Sort_Bubble;{ сортировка массива "пузырьком" по возрастанию }

const n = 10; { количество элементов в массиве }

var a:array[1..n] of integer;

   i,j,x:integer;

begin

    writeln('введите ',n,' элементов массива');

    for i:=1 to n do readln( a[i] );

    for i:=1 to n-1 do begin

        for j:=i+1 to n do begin

          if a[i]>a[j] then begin

             x:=a[i]; a[i]:=a[j]; a[j]:=x;

          end;

        end;

    end;

    writeln('после сортировки:');

    for i:=1 to n do writeln( a[i] );

end.

Шейкерная сортировка

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

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

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

Procedure Shaker_Sort(n:word;Var a:array [-400..1000] of integer);

     Var

        j,k,l,r:word;

        x:integer;

  Begin

     l:=2; r:=n; k:=n;

     Repeat

        For j:=r DownTo l Do

           If a[j-1]>a[j] Then

           begin

              x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x; k:=j;

           end;

        l:=k+1;

        For j:=l To r Do

           If a[j-1]>a[j] Then

           begin

              x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x; k:=j;

           end;

        r:=k-1;

     Until l>r

  End;{Shaker_Sort}

Пирамидальная сортировка

Пирамида определяется как последовательность ключей  hl, hl+1, ..., hr  такая, что  hi<=h2i,  hi<=h2i+1  для всякого i=l,...,r/2.

Предположим, что дана пирамида с элементами hl+1, ..., hr для некоторых значений l и r и нужно добавить новый элемент x для того, чтобы сформировать расширенную пирамиду hl, ..., hr. Новый элемент x сначала помещается в вершину дерева, а затем “просеивается” по пути, на котором находятся меньшие по сравнению с ним элементы, которые одновременно поднимаются вверх; таким образом, формируется новая пирамида.

Здесь в процедуре Heap_Sort вызывается процедура Sift, которая реализует алгоритм формирования пирамиды.

Procedure Heap_Sort(n:word;Var a: array [-400..1000] of integer);

    Var

        l,r:word;x:integer;

     Procedure Sift;

        Label 13;

        Var i,j:word;

     Begin

        i:=l; j:=2*i; x:=a[i];

        While j<=r Do

        begin

           If j<r Then

              If a[j]<a[j+1] Then j:=j+1;

           If x>=a[j] Then Goto 13;

           a[i]:=a[j]; i:=j; j:=2*i;

        end;

        13: a[i]:=x

     End;{Sift}

  BEGIN

     l:=(n div 2)+1; r:=n;

     While l>1 Do

     begin

        l:=l-1; Sift

     end;

     While r>1 Do

     begin

        x:=a[1]; a[1]:=a[r]; a[r]:=x;

        r:=r-1; Sift

     end

  END;{Heap_Sort}

Обменная сортировка разделением

Этот метод называется еще быстрой сортировкой.

Устанавливаем I=1 и J=N. Сравниваем элементы  A[I]  и  A[J].  Если {  A[I]<=A[J], то уменьшаем J на 1 и проводим  следующее сравнение элементов A[I] с A[J]. Последовательное уменьшение индекса J и сравнение указанных элементов  A[I] с A[J] продолжаем  до тех пор,  пока выполняется  условие A[I] <= A[J]. Как только A[I] станет больше A[J], меняем местами элементы A[I] с A[J], увеличиваем индекс I на 1 и продолжаем сравнение  элементов  A[I] с A[J]. Последовательное увеличение  индекса I и сравнение (элементов A[I] с A[J]) продолжаем до тех  пор, пока выполняется условие A[I] <= A[J].  Как  только A[I] станет больше A[J],  опять  меняем местами элементы A[I] с A[J], снова начинаем уменьшать J.   

Чередуя уменьшение J и увеличение I, сравнение и необходимые обмены, приходим к некоторому элементу, называемому пороговым или главным, характеризующим условие  I=J. В результате элементы массива оказываются разделенными на две части так, что все элементы слева - меньше главного элемента, а все элементы справа - больше главного элемента.   

К этим  массивам применяем рассмотренный алгоритм, получаем четыре части и т.д. Процесс закончим, когда массив A станет полностью отсортированным.

При программировании алгоритма "Быстрой сортировки" удобно использовать рекуррентные вызовы процедуры сортировки (рекурсию).

var a:array[1..10] of integer; { массив элементов }

   n:integer;

procedure QuickSort( L, R : Integer ); { Быстрая сортировка массива A[] }

var i,j,x,y : integer;

begin

 i := l; j := r;

 x := a[(l+r) div 2];

 repeat

   while (A[i]<x) do inc(i);

   while (x<A[j]) do dec(j);

   if ( i<=j ) then

   begin

     y:=A[i]; a[i]:=a[j]; a[j]:=y;

     inc(i); dec(j);

   end;

 until (i>j);

 if (l<j) then QuickSort(l,j);

 if (i<r) then QuickSort(i,r);

end;

begin

    writeln('введите 10 элементов массива:');

    for n:=1 to 10 do readln(a[n]);

    QuickSort( 1, 10 ); { на входе: левая и правая граница сортировки }

    writeln('после сортировки:');

    for n:=1 to 10 do writeln(a[n]);

end.Procedure Quick_Sort(n:word;Var a:massiv);

     Procedure Sort1(l,r:word);

        Var

           w,x:integer;

           i,j:word;

     Begin

        i:=l; j:=r;

        x:=a[(l+r) div 2];

        Repeat

           While a[i]<x Do i:=i+1;

           While a[j]>x Do j:=j-1;

           If i<=j Then

              begin

                 w:=a[i]; a[i]:=a[j]; a[j]:=w;

                 i:=i+1; j:=j-1

              end

        Until i>j;

        If l<j Then Sort1(l,j);

        If i<r Then Sort1(i,r);

     End;{Sort1}

  BEGIN

     Sort1(1,n);

  END;{Quick_Sort}

Задачи для индивидуального решения

  1.  Отсортировать строки массива целых чисел по убыванию. Сортировка включением.
  2.  Отсортировать столбцы массива целых чисел по возрастанию. Шейкерная сортировка.
  3.  Отсортировать нечетные столбцы массива по возрастанию. Сортировка прямой выбор.
  4.  Отсортировать элементы нечетных строк массива целых чисел по убыванию. Сортировка разделением.
  5.  Отсортировать элементы квадратной вещественной матрицы размерности n, применив сортировку бинарным включением.
  6.  Отсортировать элементы квадратной вещественной матрицы размерности n, применив пузырьковую сортировку.
  7.  Отсортировать положительные элементы одномерного массива, отрицательные оставить на местах. Пузырьковая сортировка.
  8.  Отсортировать строки массива целых чисел по убыванию. Шейкерная сортировка.
  9.  Отсортировать столбцы массива целых чисел по возрастанию. Сортировка включением.
  10.  Отсортировать нечетные столбцы массива по возрастанию. Сортировка разделением.
  11.  Отсортировать элементы нечетных строк массива целых чисел по убыванию. Сортировка прямой выбор.
  12.  Отсортировать элементы квадратной вещественной матрицы размерности n, применив пузырьковую сортировку  слева направо.
  13.  Заданный одномерный массив отсортировать по возрастанию цифры десятков каждого элемента. Сортировка прямой выбор.
  14.  Отсортировать элементы квадратной вещественной матрицы размерности n, стоящие на побочной диагонали, применив сортировку бинарным включением.
  15.  Заданный одномерный массив отсортировать по возрастанию цифры десятков каждого элемента. Сортировка включением.
  16.  В одномерном массиве упорядочить отрицательные элементы, оставив положительные на местах. Сортировка включением.
  17.  В одномерном массиве упорядочить нечетные элементы, оставив четные на местах. Сортировка прямой выбор.
  18.  Упорядочить одномерный массив так, чтобы в начале располагались четные элементы в порядке возрастания их значений, а затем нечетные – в порядке убывания их значений.
  19.  В одномерном массиве упорядочить нечетные элементы, оставив четные на местах. Сортировка шейкерная.
  20.  Отсортировать положительные элементы одномерного массива, отрицательные оставить на местах. Сортировка прямой выбор.
  21.  Отсортировать строки массива целых чисел по убыванию. Шейкерная сортировка.
  22.  Отсортировать столбцы массива целых чисел по возрастанию. Сортировка включением.
  23.  Отсортировать нечетные столбцы массива по возрастанию. Сортировка разделением.
  24.  Отсортировать элементы нечетных строк массива целых чисел по убыванию. Сортировка прямой выбор.
  25.  Отсортировать элементы квадратной вещественной матрицы размерности n, стоящие на главной диагонали, применив пузырьковую сортировку  слева направо.
  26.  Заданный одномерный массив отсортировать по возрастанию цифры десятков каждого элемента. Сортировка прямой выбор.
  27.  Отсортировать элементы квадратной вещественной матрицы размерности n, стоящие на побочной диагонали, применив сортировку бинарным включением.
  28.  Заданный одномерный массив отсортировать по возрастанию цифры десятков каждого элемента. Сортировка включением.
  29.  В одномерном массиве упорядочить отрицательные элементы, оставив положительные на местах. Сортировка включением.
  30.  В одномерном массиве упорядочить нечетные элементы, оставив четные на местах. Сортировка прямой выбор.


 

А также другие работы, которые могут Вас заинтересовать

75680. Стилистическое использование однородных членов предложения 76.47 KB
  Особая полнота и точность перечисления однородных понятий обязательное требование к языку законов постановлений в официально-деловом стиле: Все граждане имеют равные права в семейных отношениях. Блоки однородных членов в книжных стилях строятся как правило из словоформ обозначающих однотипные понятия. В книжных стилях перечисление нередко выглядит как длинная цепочка однородных членов причем в их сочиненном ряду как правило преобладает бессоюзная связь.
75681. Стилистическое использование различных типов сложного предложения 88.91 KB
  Не останавливаясь подробно на синтаксисе устной формы разговорной речи отметим что при письменном ее отражении в художественных текстах и прежде всего в драматургии наиболее широко используются бессоюзные сложные предложения. Попробуем предикативные единицы объединенные в сложные бессоюзные предложения в цитированном отрывке связать с помощью союзов: Думаю что ничего у нас не выйдет. У него дела много так что ему не до меня поэтому и внимания не обращает. Из этого конечно не следует что в художественной речи отражающей...
75682. Стилистическая оценка параллельных синтаксических конструкций 127.53 KB
  Редактор прочитал рукопись и написал рабочую рецензию. Редактор прочитав рукопись написал рабочую рецензию. Редактор прочитавший рукопись написал рабочую рецензию. Редактор закончил чтение рукописи и приступил к написанию рабочей рецензии.
75683. Стилистическая оценка заимствованных слов 118.35 KB
  Заимствования из древних языков греческого латинского тюркизмы галлицизмы слова из голландского немецкого английского полонизмы украинизмы и др. В средствах массовой информации полюбили слова популизм популист используя их однако совсем не так как это принято на Западе. Примеров такого толкования слова можно привести множество вот один из них: . Словари иностранных слов не успевают освоить новые заимствования поэтому читатель не владеющий английским нередко оказывается беспомощным встречая непонятные слова в газетах...
75684. Лексические образные средства 219.96 KB
  Понятие образности речи Слова образность образный используются в стилистике в разных значениях. Образность в широком смысле этого слова как живость наглядность красочность изображения неотъемлемый признак всякого вида искусства форма осознания действительности с позиций какого-то эстетического идеала образность речи частное ее проявление. Стилистика рассматривает образность речи как особую стилевую черту которая получает наиболее полное выражение в языке художественной литературы. Более узкое понимание образности речи основано...
75685. Фоника. Понятие фоники. Значение звуковой организации речи 365.48 KB
  Понятие фоники Фоника раздел стилистики изучающий звуковую сторону речи. В отличие от фонетики представляющей собой раздел языкознания который изучает способы образования и акустические свойства звуков того или иного языка фоника наука об искусстве звуковой организации речи. Под фоникой понимают также звуковую организацию речи т. При этом говорят о фонике того или иного произведения исследуя например фонику поэмы стихотворения анализируя эстетическую функцию различных фонетических средств прежде всегозвуков речи.
75686. СТИЛИСТИКА СЛОВООБРАЗОВАНИЯ 189.65 KB
  Русский язык отличается исключительным богатством словообразовательных ресурсов, обладающих яркой стилистической окраской. Это обусловлено развитой системой русского словообразования, продуктивностью оценочных суффиксов, придающих словам разнообразные экспрессивные оттенки
75687. Стилистика имени числительного 164.35 KB
  Однако этот графический способ обозначения числа количества здесь уже не является единственным: параллельно могут быть использованы и словесные обозначения чисел количества что открывает пути к функционально-стилевому применению числительных.
75688. Стилистика местоимения. Употребление местоимений в разных стилях речи 158.67 KB
  Употребление местоимений в разных стилях речи При функционально-стилевой характеристике местоимений прежде всего обращает на себя внимание их особая употребительность в разговорной речи. В разговорной речи употребление местоимений сопровождается различными приемами их актуализации; ср. плеонастическое употребление местоимений при указании на субъект действия: Дима он не подведет или конструкции типа: Так оно и было; Идет она прическа платье все у нее по моде. Использование местоимений в разговорном стиле отличает также свойственная...