Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Тема: Разработка программ с использованием методов сортировки
Цель работы: Сформировать знания и умения по изучению методов внутренних сортировок. Приобретение навыков реализации алгоритмов сортировок.
Время выполнения: 2 часа.
Порядок выполнения работы:
Теоретические сведения
Существует три группы методов внутренней сортировки (сортировка включением, сортировка выбором, обменная сортировка).
Сортировка прямым включением. Элементы условно разделяют на готовую 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}
Задачи для индивидуального решения