78180

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

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

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

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

Русский

2015-02-07

77 KB

2 чел.

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

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

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


 

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

64275. ПІДВИЩЕННЯ НАДІЙНОСТІ ЗБІРНИХ ТВЕРДОСПЛАВНИХ РІЗЦІВ ВАЖКИХ ТОКАРНИХ ВЕРСТАТІВ 241 KB
  Тому наукове обґрунтування технології та режимів МІО вибір раціональних конструктивних параметрів інструменту підвищення його надійності є актуальною задачею. Від цього залежать характер протікання процесу різання забезпечення надійності роботи як різального інструменту...
64276. КЛІНІКО-ЕКСПЕРИМЕНТАЛЬНЕ ОБГРУНТУВАННЯ ПРОФІЛАКТИЧНИХ ЗАХОДІВ ПРИ ЛЕПТОСПІРОЗІ СВИНЕЙ 467.5 KB
  Лептоспіроз – одна з найбільш поширених антропозоонозних інфекцій, тому, зважаючи на природну вогнищевість та прихований перебіг серед свинопоголів’я, дослідження цього захворювання особливо важливе.
64277. ОЦІНКА ЕФЕКТИВНОСТІ ДІЯЛЬНОСТІ ПІДПРИЄМСТВА: ВАРТІСНО-ОРІЄНТОВАНИЙ ПІДХІД 323 KB
  Важливого значення набувають також проблемні питання вибору інтегрального критерію ефективності діяльності підприємства на який необхідно орієнтуватися менеджменту для оперативного прийняття господарських рішень...
64278. Влияние добавок водорода на технико-экономические и экологические показатели газовых и дизельных двигателей 763.5 KB
  Одним из направлений уменьшения токсичности ОГ и повышения топливной экономичности ДВС является применение водорода как в чистом виде так и совместно с углеводородным топливом.
64279. Антенные решетки, синтезированные по широкополосному сигналу, для средств связи беспилотных авиационных комплексов 241.5 KB
  Объект исследования антенные устройства наземной и бортовой составляющих в составе указанных комплексов. Задача решаемая в диссертации состоит в разработке методов повышения энергетического потенциала и помехозащищенности линии связи с беспилотным летательным аппаратом...
64280. МОДЕЛІ АРХІТЕКТУРНИХ РІШЕНЬ ТА МЕТОДИ ЇХ ОЦІНКИ В ПРОЦЕСІ РЕІНЖИНІРИНГУ ІНФОРМАЦІЙНИХ СИСТЕМ ОРГАНІЗАЦІЙНОГО УПРАВЛІННЯ 3.38 MB
  Цей контекст визначає важливість задачі забезпечення ефективної трансформації архітектури інформаційної системи. Саме адекватна архітектурна модель та її послідовна реалізація в процесі розробки інформаційної системи забезпечує логічну цілісність проекту...
64281. РОЗРОБКА ТЕХНОЛОГІЇ КОВБАСНИХ ВИРОБІВ ЗІ ЗНИЖЕНИМ ВМІСТОМ НІТРИТУ 205.5 KB
  Метою роботи є наукове обґрунтування та розробка технології варених варенокопчених та сирокопчених ковбасних виробів зі зниженим вмістом нітриту натрію за...
64282. ОЦІНЮВАННЯ ОБМЕЖЕНЬ У ВИКОРИСТАННІ ЕКОНОМІЧНОГО ПОТЕНЦІАЛУ ПІДПРИЄМСТВА 147 KB
  При цьому ряд ознак впливу цих чинників інтенсивність тривалість і сила впливу та його негативний характер дозволяє стверджувати вже не про тимчасовий негативний вплив окремого чинника або їх групи а про існування...
64283. УКРАЇНСЬКЕ ПОРІВНЯЛЬНЕ ЛІТЕРАТУРОЗНАВСТВО КІНЦЯ ХІХ - ПЕРШОЇ ТРЕТИНИ ХХ СТ.: ТЕОРЕТИКО-МЕТОДОЛОГІЧНИЙ ДИСКУРС 303 KB
  Для сучасного літературознавства характерне розмаїття поглядів та співіснування різних течій, напрямів, шкіл. Посилюється інтерес до інтердисциплінарних, рецептивних, феноменологічних досліджень; вагомою є теорія дискурсу архетипів, концептів...