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


 

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

35674. Тихий Океан. Творчий проект 3.55 MB
  2 Донні осідання 5 Клімат 6 Гідрологічний режим 7 Крига 8 Флора і фауна 9 Економіка 10 Дослідження океану 10. Раніше акваторія Тихого океану частіше підрозділялася на три частини: північну центральну і південну межами між якими служили Північний і Південний тропіки. Окремі ділянки океану розташовані між островами або виступами суші мають свої назви. У західній і південнозахідній частинах Тихого океану численні крупні острови відокремлюють від основної акваторії безліч міжострівних морів таких як Тасманове море на південний схід...
35676. Скринька для ключів. Творчий проект 2.29 MB
  Мотивація вибору форми виробу. Мотивація вибору форми виробу Людина щоб облаштувати своє житло здавна навчилася виготовляти різні речі з каменю дерева а пізніше з металу. Через те коли виникла необхідність виготовити річ для зберігання ключів я й вибрав деревину як матеріал для свого майбутнього виробу. Чому Вважаю що майстер не завжди повинен дотримуватися якихось обмежених рамок у виготовленні того чи іншого виробу.
35678. Изучение аппаратного и программного обеспечения персонального компьютера 477.9 KB
  Запоминающее устройство - носитель информации, предназначенный для записи и хранения данных. В основе работы запоминающего устройства может лежать любой физический эффект, обеспечивающий приведение системы к двум или более устойчивым состояниям.
35680. Моя професійна кар’єра. Творчий проект 1.75 MB
  План роботи над проектом: Моє професійне самовизначення Додаток : Топ 20 найперспективніших Загальні відомості про дану професію: Завдання та обовязки; Вимоги до робітника; Особистості якості робітника. І найголовніше: людина повинна отримувати задоволення від своєї роботи Серед усіх пяти основних типів професій найбільше мені підходять людинатехніка до цього типу належать професії: водій машиністи потягів оператори верстатів з програмованим управлінням інженери слюсарі тощо. Умови роботи: Повна...
35682. Інформаційно-пошуковий проект «Олександр Матросов. 70 років подвигу» 36.14 KB
  Обґрунтування актуальності проекту Сучасна школа спрямована на забезпечення всебічного розвитку особистості шляхом навчання та виховання які ґрунтуються на загальнолюдських цінностях та принципах науковості інтегрованості єдності навчання і виховання на засадах гуманізму демократії громадянської свідомості взаємоповаги в інтересах людини родини суспільства держави. І саме тому я запропонувала своїм учням залучитися до реалізації цільового творчого проекту з громадянськопатріотичного виховання Олександр Матросов 70 років подвигу ....