7.3.4. Быстрая сортировка

Данный алгоритм является самым эффективным методом внутренней сортировки и поэтому имеет название "быстрая сортировка".¹ В этом алгоритме для сортировки элементов массива А[1], ..., А[n] из этих элементов выбирается некоторое значение ключа v в качестве опорного элемента, относительно которого переупорядочиваются элементы массива. Желательно выбрать опорный элемент близким к значению медианы распределения значений ключей так, чтобы опорный элемент разбивал множество значений ключей на две примерно равные части. Далее элементы массива переставляются так, чтобы для некоторого индекса j все переставленные элементы А[1], ..., A[j] имели значения ключей, меньшие, чем v, а все элементы A[j + 1], ..., А[n] — значения ключей, большие или равные v. Затем процедура быстрой сортировки рекурсивно применяется к множествам элементов А[1], ..., A[j] и A[j + 1], ..., А[n] для упорядочивания этих множеств по отдельности. Поскольку все значения ключей в первом множестве меньше, чем значения ключей во втором множестве, то исходный массив будет отсортирован правильно.

Задача 7.13. Дан целочисленный массив размерностью 10 элементов. Упорядочить элементы данного массива по возрастанию посредством быстрой сортировки.

Листинг программы

program task4;

uses crt;

const n = 10;

type vector = array [ 1..n] of integer;

var a : Vector;

i, j : integer;

temp : integer;

procedure QuickSort;

procedure sort (l, r : integer);

var i, j, w, x : integer;

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 sort(l,j);

if i < r then sort(i,r);

end;

begin

sort (1,n);

end;

begin

clrscr;

randomize;

for i :=1 to n do

begin

a[i] := random(11)-5;

writeln ('a[', i, ']=', a[i]:3);

end;

quicksort;

writeln ('Отсортированный массив по возрастанию');

for i := 1 to n do

writeln ('a[', i, ']=', a[i]:3);

readln;

end.

8. Составление программ с использованием подпрограмм

Паскаль – структурированный язык, где программа может состоять из отдельных модулей. Каждый модуль – это подпрограмма, которая представляет собой самостоятельный фрагмент программы реализации определённой задачи, и может быть связана с основной программой лишь с помощью нескольких параметров. Отсюда, в структурированных программах легко прослеживается основной алгоритм. Отладка самостоятельных единиц не приводит к изменению основной программы.

Применение подпрограмм даёт следующие преимущества:

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

2. Заключается в применении методики нисходящего проектирования программ. В этом случае алгоритм представляется в виде последовательности относительно крупных подпрограмм, реализующих самостоятельные смысловые части алгоритма. Подпрограммы в свою очередь разбиваются на менее крупные подпрограммы нижнего уровня и т. д. Последовательное структурирование программы продолжается до тех пор, пока реализуемые подпрограммами алгоритмы не станут настолько простыми, чтобы их можно было легко запрограммировать. Такие программные единицы легче тестировать и отлаживать, и у них более чёткая логическая структура.

Для организации структурной программы используют подпрограммы, которые делятся на пользовательские и стандартные, последние находятся в модуле turbo.tpl. Например, в модуле CRT находится процедура очистки экрана – CLRSCR; и процедура, отвечающая за цвет выводимого текста – TEXTCOLOR (). Стандартные процедуры – READ, WRITE и функции – SIN, ORD, CHR.

Каждая подпрограмма состоит из набора операторов, которые снабжены одним именем. По этому имени происходит обращение к данной подпрограмме.

По способу организации подпрограммы делятся на подпрограммы-процедуры – PROCEDURE и п одпрограммы – функции – FUNCTION (причём, функция – частный случай процедуры).

Описать подпрограмму – это означает, в разделе описаний основной программы после раздела объявления переменных (VAR) указать заголовок и тело программной единицы. В заголовке объявляются имя подпрограммы и формальные параметры, если они есть. Для функции указывается, кроме того, и тип возвращаемого ею результата. За заголовком следует тело подпрограммы, которое, подобно основной программе, состоит из раздела описаний и раздела исполняемых операторов. В разделе описаний подпрограммы могут встретиться описания подпрограмм низшего уровня, в тех – описания других подпрограмм и так далее. Все имена, описанные внутри программной единицы, локализуются в ней, то есть «невидимы» снаружи программы.

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

Структура основной программы с использованием подпрограмм

PROGRAM <имя_программы>;{Заголовок основной программы}

L ABEL

CONST

TYPE

VAR

PROCEDURE <имя_процедуры> (<список_формальных_параметров>);

LABEL

C ONST

TYPE

VAR

BEGIN

{тело процедуры}

END;

FUNCTION <имя_функции> (<список_формальных_параметров>): <тип_возвращаемого_результата>;

LABEL

CONST

TYPE

VAR

BEGIN

{тело функции}

END;

BEGIN

{тело основной программы}

E ND.