78180

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

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

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

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

Русский

2015-02-07

77 KB

7 чел.

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

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

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


 

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

36290. Задачи администратора базы данных 35 KB
  Администрирование базами данных предусматривает выполнение функций направленных на обеспечение надежного и эффективного функционирования системы баз данных адекватности содержания базы данных информационным потребностям пользователей отображения в базе данных актуального состояния предметной области. Администратор базы данных это: управляющий данными а не хозяин; системный программист определенного профиля а также эксперт высшего уровня обеспечивающий службу эксплуатации решениями по процедурам и регламентам работы; лицо принимающее...
36291. Понятие транзакции 38.5 KB
  Понятие транзакции. Транзакции несколько операторов языка SQL которые либо все выполняются по очереди либо все не выполняются. Согласованность гарантия что по мере выполнения транзакции данные переходят из одного согласованного состояния в другое.
36292. Журнализация изменений БД, файл журнала, контрольные точки 31.5 KB
  Это требование предполагает возможность восстановления согласованного состояния базы данных после любого программного или аппаратного сбоя. Типичная СУБД должна предоставлять такие функции восстановления как: механизм резервного копирования предназначенный для периодического создания копий базы данных; средства ведения журнала в котором фиксируются текущее состояние транзакций и вносимые в базы данных изменения; функция создания контрольных точек обеспечивающая перенос выполняемых в базе данных изменений во вторичную помять с целью...
36293. Восстановление базы данных 28 KB
  При этом надо устранить последствия операторов модификации базы данных которые выполнялись в этой транзакции. Ситуация характеризуется потерей той части базы данных которая к моменту сбоя содержалась в буферах оперативной памяти. Восстановление после поломки основного внешнего носителя базы данных жесткий сбой.
36294. Техническое задание. Основные разделы 36.5 KB
  Техническое задание это документ определяющий цели требования и основные исходные данные необходимые для разработки автоматизированной системы управления. требования к программе или программному изделию; требования к функциональным характеристикам; требования к составу выполняемых функций организации входных и выходных данных временным характеристикам требования к надежности; требования к обеспечению надежного функционирования обеспечения устойчивого функционирования контроль входной и выходной информации время восстановления...
36295. Состав и содержание работ на стадиях внедрения, эксплуатации и сопровождения проекта 39.5 KB
  Недостатком первого подхода является увеличение длительности внедрения что ведет за собой рост стоимости проекта. При использовании второго подхода сокращается время внедрения но возникает возможность пропуска ошибок в проектной документации поэтому чаще всего используют смешанный метод внедрения проекта ЭИС. Внедрение проекта осуществляется в течение трех этапов: подготовка объекта к внедрению; опытное внедрение; сдача проекта в промышленную эксплуатацию.
36296. САSЕ – средства, классификация 26 KB
  Аббревиатура САSЕ Соmputеrаidеd Softwre Епgineering автоматизированная разработка ПО обозначает специальный тип программного обеспечения предназначенного для поддержки отдельных этапов создания ПО таких как разработка требований проектирование кодирование и тестирование программ. Поэтому к САSЕсредствам относятся редакторы проектов словари данных компиляторы отладчики средства построения систем и т. САSЕтехнологии предлагают поддержку процесса создания ПО путем автоматизации которых этапов разработки а также создания и...