Реализация алгоритмов сортировок включением и выбором при написании программы на Паскале

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

Краткие теоретические сведения

Под сортировкой понимают процесс переупорядочивания некоторого множества объектов с целью их размещения в заданном порядке. Это универсальный вид деятельности с точки зрения обработки данных, которые представляют собой последовательность ключей. С помощью сортировки добиваются такого их размещения, чтобы было выполнено условие:

f(a[1]) f(a[2])f(a[3])… f(a[N]),

где символ означает знак предшествования, а f -некоторая функция упорядочивания. При упорядочивании по возрастанию, после сортировки будет выполнено условие:

a[1] a[2] a[3] ... a[N]

В ходе сортировки элементы последовательности меняются местами. Сортировка называется устойчивой, если на этапе замены два одинаковых ключа не меняются местами. Сортировка называется внутренней, если все сортируемые ключи размещаются в оперативной памяти. Если некоторая часть ключей размещается на внешнем носителе, то сортировка называется внешней.

Методы внутренней сортировки

В данных лабораторно-практических работах будут рассмотрены методы, у которых на входе - вектор с произвольным положением ключей, а на выходе - этот же вектор упорядочен по возрастанию.

Существует три группы методов внутренней сортировки (сортировка включением, сортировка выбором, обменная сортировка). В данной лабораторной работе рассмотрены методы сортировки включением и выбором.

Сортировки включением

Сортировка прямым включением. Элементы условно разделяют на готовую a[1],...,a[i-1] и входную последовательности a[i],...,a[n]. Сначала i=2. На каждом шаге, увеличивая i на единицу, берут i-й элемент входной последовательности и передают в готовую последовательность, вставляя на подходящее место.

Итак, в начале рассматривается второй элемент (i=2) последовательности ключей. Он сравнивается с первым элементом (a[i-1]) и если он его меньше, то они меняются местами. В противном случае проход заканчивается, i увеличивается на 1 и процесс повторяется. Заметим, что упорядоченная последовательность a[i-1] называется готовой последовательностью и новый элемент вставляется в готовую последовательность на свое место.

На каждом проходе происходит перемещение i -того элемента в готовую последовательность, а некоторое число элементов сдвигается вправо. Данный процесс перемещения называется просачиванием элемента.

Здесь и далее, во всех процедурах сортировки ключи упорядочиваются по возрастанию. На входе процедур - количество элементов массива ( n ), на выходе - упорядоченный массив элементов(а).

Procedure Straight_Insertion(n:integer; Var a:t);

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}

Процедура упорядочивает элементы массива начиная с первого. Нулевой элемент используется процедурой как вспомогательный.

В основной программе массив необходимо объявить следующим образом:

TYPE

t=array[0..20] of integer;

VAR

A:t;

N,i:word;

Ввод массива:

FOR i:=1 to n do

Read(a[i]);

Вывод отсортированного массива:

FOR i:=1 to n do

Wrire(a[i],’ ‘);

Сортировка бинарными включениями. Алгоритм сортировки прямыми включениями можно легко улучшить, пользуясь тем, что готовая последовательность a[1],...,a[i-1], в которую нужно включить новый элемент, уже упорядочена. Поэтому место включения можно найти значительно быстрее, применив бинарный поиск, который исследует средний элемент готовой последовательности и продолжает деление пополам, пока не будет найдено место включения. Модифицированный алгоритм сортировки называется сортировкой бинарными включениями.

Procedure Binary_Insertion(n:word;Var a:t);

Var

i,j,k,r,m:word;

x:integer;

Begin

For i:=2 To n Do

begin

x:=a[i]; k:=1; r:=i-1;

While k<=r Do

begin

m:=(k+r) div 2;

If x<a[m] Then r:=m-1

Else k:=m+1

end;

For j:=i-1 DownTo l Do a[j+1]:=a[j];

a[k]:=x

end;

End; {Binary_Insertion}

Сортировка выбором

Прямой выбор. Этот метод основан на следующем правиле: выбираем элемент с наименьшим ключом. Он меняется местами с первым элементом. Эти операции затем повторяются с оставшимися n -1 элементами, затем с n -2 элементами, пока не останется только один элемент - наибольший. Этот метод называемый сортировкой простым выбором, в некотором смысле противоположен сортировке простыми включениями; при сортировке простым выбором рассматриваются все элементы входного массива для нахождения элемента с наименьшим ключом, и этот один очередной элемент отправляется в готовую последовательность.

Procedure Straight_Selection(n:word;Var a:t);

Var

i,j,k:word;

x:integer;

Begin

For i:=1 To n-1 Do

begin

x:=a[i]; k:=i;

For j:=i+1 To n Do

If x>a[j] Then

begin

k:=j; x:=a[j];

end;

a[k]:=a[i]; a[i]:=x;

end

End;{Straight_Selection}

Порядок выполнения работы

1. Изучить теоретические сведения по теме: ”Алгоритмы сортировок включением и выбором”

2. Разработать программу для реализации рассмотренных в данной работе методов сортировок. Предоставить пользователю возможность выбора метода сортировки.

3. Показать работающую программу преподавателю.

4. Ответить на контрольные вопросы.

Контрольные вопросы

1. Понятие сортировки. Виды сортировок.

2. Сортировки включением. Описание алгоритмов методов сортировки прямыми и бинарными включениями.

3. Сортировки включением. Описание алгоритмов методов сортировки прямыми и бинарными включениями.

4. Сортировка выбором. Описание алгоритма.

5. Фрагменты программ для реализации данных методов сортировок.

 

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