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.  В одномерном массиве упорядочить нечетные элементы, оставив четные на местах. Сортировка прямой выбор.


 

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

4817. Отчетность коммерческих банков 172 KB
  Отчетность коммерческих банков Сущность и цели подготовки банковской отчетности Система банковской финансовой отчетности Вопрос 1. Сущность и цели подготовки банковской отчетности Банковская отчетность - это единая система количест...
4818. Международный суд и его деятельность 170 KB
  Международный суди его деятельность Международный Суд, согласно пункту 1 статьи 7 Устава ООН, является одним из главных судебных органов Организации Объединенных Наций. Исходя из статьи 92 Устава ООН, Международный Суд является главным судебны...
4819. Система AutoCAD. Курс лекций 2.86 MB
  Команды общего редактирования. Кнопка ERASE Команды стереть – стирает с экрана выбранные объекты и удаляет их из рисунка. Можно использовать ручки. выделить ручками объект или мышью, и нажать на клавишу Delete. Кнопка команды копирова...
4820. Исследование и анализ режимов работы источника постоянной ЭДС 131.5 KB
  Исследование и анализ режимов работы источника постоянной ЭДС Цель работы. Изучение и анализ различных режимов работы источника электродвижущей силы (источника ЭДС) Основы теории. Системы электроизмерительных приборов. Приборы магн...
4821. Геометрия Лобачевского. Геометрия кривых поверхностей 31.5 KB
  Геометрия Лобачевского. Н.И. Лобачевскийв 1826г. впервые построил и развил одну из возможных геометрий, где аксиома (А) не имеет места. Геометрия Лобачевского основывается на тех же аксиомах, что и евклидова геометрия, за исключением аксиомы о парал...
4822. Основные понятия и принципы системы Delphi 454 KB
  Основные понятия и принципы системы Delphi. Цель: Дать студентам общие сведения об объектно-ориентированном языке программирования Delphi. План занятия. Организационный момент. Изучение нового материала. Контрольные вопросы. ...
4823. Основы программирования на языке Turbo Pascal 246 KB
  Основы программирования Цель: Дать студентам основы программирования. Задачи: Воспитательная: повторение уже изученного языка программирования TurboPascal. Учебная: научить правильно применять константы и переменные. Развивающая: развитие вним...
4824. Создание первой программы на языке Turbo Pascal 184 KB
  Создание первой программы. Цель: Показать студентам пример создания программы. Задачи: Воспитательная: повторение уже изученного языка программирования TurboPascal. Учебная: научить создавать программы. Развивающая: развитие внимательности. Пл...
4825. Создание первой программы в языке Turbo Pascal 94.5 KB
  Создание первой программы. Цель: Показать студентам управление программой при помощи меню. Задачи: Воспитательная: повторение уже изученного языка программирования TurboPascal. Учебная: научить создавать программы. Развивающая: развитие внимат...