Алгоритмы основных методов сортировок

(Для всех случаев как пример рассмотрена сортировка чисел по возрастанию).

Алгоритм сортировки выбором.

Это метод сортировки на месте (в одном массиве). В массиве ищется минимальный элемент и переставляется на место первого элемента (а первый элемент – на место найденного минимального). Потом этот процесс повторяется, но массив рассматривается со второго элемента (первый уже на месте). Найденный минимальный элемент меняется местами со вторым. Это повторяется до (n–1)-го элемента (n-ый элемент автоматически окажется на месте). Примечание: при поиске минимального элемента нужно находить и запоминать его место – для перестановки элементов.

Пример алгоритма на языке Паскаль для массива А длиной N чисел:

 

for i:=1 to N-1 do

Begin

{ поиск места, где находится минимальный элемент }

imin:=i;

for j:=imin+1 to N do

if A[j]<A[imin] then

imin:=j;

{ перестановка i-го и минимального элементов }

r:=A[i];

A[i]:=A[imin];

A[imin]:=r;

end;

 

 

Алгоритм сортировки обменом.

Это также метод сортировки на месте (в одном массиве); некоторые алгоритмы этого метода носят название метода пузырька. Сравниваются два соседних элемента (первый и второй), если они в правильном порядке – ничего не делается, если порядок нарушен – они меняются местами. Потом этот процесс повторяется для второго и третьего элементов, и так до конца (n–1 и n-ый элементы). В результате самый большой элемент оказывается в самом конце (на n-ом месте). Затем весь этот процесс повторяется, но уже до n–1-го элемента (так как n-ый уже на месте); затем – до n–2-го и так всего n–1 раз. Тем самым n–1 элементов снизу окажутся упорядоченными, а следовательно и первый элемент тоже.

Пример:

for i:=1 to N-1 do

for j:=1 to N-i do

if A[j]>A[j+1] then { если два соседних элемента идут по убыванию }

begin { перестановка j-го и следующего элементов }

r:=A[j];

A[j]:=A[j+1];

A[j+1]:=r;

end;

Алгоритм сортировки вставками.

Этот метод относится к сортировкам в двух массивах. Имеется два массива. Один заполнен неупорядоченными числами, второй – пустой. Из первого берется первое число и переписывается на первое место во второй массив. Берется второе число и сравнивается с переписанным во второй массив. Если уже записанное число больше второго, оно переписывается на одну позицию ниже (на второе место), а последнее взятое число – на место первого. Затем из исходного массива берется третье число и сравнивается со вторым из выходного массива. Если оно должно вставляться выше второго, второе переписывается на позицию ниже. Далее сравнение проводится с первым числом и, если вставляемое число больше или равно первому, оно записывается на место, освободившееся от второго числа, иначе первое переписывается на позицию ниже, а вставляемое – на его место. Процесс повторяется, пока не будут вставлены на нужные места во второй массив все числа из первого.

Пример:

 

for i:=1 to N do { каждый элемент массива А вставляем в массив В

Разыскивая (снизу вверх в упорядоченной части массива В) место,

Куда его надо вставить. При этом элементы массива В сдвигаются

вниз по одному, освобождая место для вставляемого A[i] }

Begin

j:=i-1; { если вставляем i-й элемент массива А, значит в массиве

В уже лежат i-1 элемент }

while (j>0) and (B[j]>A[i]) do

Begin

B[j+1]:=B[j]; { сдвиг элемента массива В вниз }

j:=j-1;

end;

B[j+1]:=A[i]; { запись A[i] на освободившееся место в массив В }

end;

 

Алгоритм сортировки пересчетом.

Этот метод относится к сортировкам в двух массивах. Берется первый элемент исходной последовательности и подсчитывается, сколько элементов имеют величину, меньшую чем взятый. Проверяемый элемент помещается в выходной массив на место, равное подсчитанному числу плюс один (но если в этом месте уже записано число – то на следующее место). Это проделывается для следующего элемента исходной последовательности, и так до конца. В выходном массиве элементы упорядочены. Чтобы определить, занято ли место в выходном массиве, его предварительно следует заполнить "признаком свободного места" – таким числом, которого нет в сортируемом массиве. В качестве такого числа можно взять значение, например, на единицу больше максимального числа в сортируемом массиве.

 

{ поиск числа, которым заполним выходной массив В в качестве признака

Незанятого элемента. В качестве такого числа возьмем число, на 1

больше максимального значения из массива А }

Max:=A[1]; { поиск максимума из А }

for i:=2 to N do

if A[i]>Max then

Max:=A[i];

Pr:=Max+1;

{ Заполнение массива В признаком "свободно" }

for k:=1 to N do

B[k]:=Pr;

{ Собственно сортировка пересчетом }

for i:=1 to N do

Begin

{ поиск места "k" в массиве В на которое пртендует A[i] - выполняем

подсчетом, сколько чисел в массиве А меньше чем рассматриваемый A[i] }

k:=1;

for j:=1 to N do

if A[j]<A[i] then

inc(k);

{ если k-тое место в массиве В занято (таким же значением) сдвигаемся

ниже по массиву В, пока не встретим в нем незанятую ячейку (=Pr).

Это необходимо, если в массиве А могут встречаться одинаковые значения,

претендующие на одно и то же место в В }

while B[k]<>Pr do

inc(k);

B[k]:=A[i]; { записываем A[i] на найденное место в массив В }

end;

 

 

Сортировка слиянием.

Этот метод предполагает, что имеется два или несколько наборов данных, каждый из которых уже упорядочен. Нужно объединить их в один упорядоченный набор данных. Как входные, так и выходной наборы могут размещаться во внешней памяти (в файлах). Алгоритм заключается в том, что заводится столько указателей, сколько входных наборов данных объединяется одновременно; каждый указатель сначала указывает на первый элемент в каждом наборе. Выбирается самый маленький элемент из тех, на которые указывают эти указатели, и он переписывается в выходной массив, после чего указатель набора, из которого был переписан элемент, увеличивается на единицу (и теперь указывает на второй элемент этого набора). Далее снова производится выбор наименьшего элемента из тех, на которые указывают указатели, и так пока не будут выбраны все элементы из всех наборов. Если кончается один из наборов, а их всего два, то оставшиеся элементы второго набора дописываются в конец выводного файла.

Если сливаются одновременно более двух наборов, вычерпанный набор перестает рассматриваться при выборе минимального элемента, или в этом наборе искусственно создается дополнительный элемент с очень большим ключом (каких не может быть у реальных элементов) и при выборе он никогда не будет взят. При этом не меняется схема выбора. Если первоначально было N упорядоченных коротких наборов данных, то объединяя их попарно этим методом, после первого прохода станет N/2 упорядоченных наборов, но каждый из них будет уже в два раза длиннее. Повторяя этот процесс и беря каждый раз выходные наборы в качестве входных для слияния, можно в итоге получить один упорядоченный набор. Первоначальные N наборов можно получить из исходного, например, беря по паре элементов, поменяв их местами, если они не в правильном порядке.

 

Строки

Строковые переменные

 

Некоторой особой разновидностью одномерных символьных массивов являются специальные составные объекты Паскаля, называемые строками. Их частое использование и специальный набор процедур и функций, работающих со строками, позволяет выделить их в отдельный составной тип.

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

Значения строк в программе записываются в виде последовательности символов, заключенных в апострофы. Количество символов в строке может меняться от 0 до максимального, предусмотренного при выделении места под строку. Если при создании строки ее максимальная длина не оговаривается, она считается равной максимальному значению, равному 255 символов. Текущая длина строки хранится в виде однобайтного целого в нулевом байте строки. Поэтому в памяти ЭВМ строка занимает на 1 байт больше места, чем указано в ее максимальной длине.

Для того чтобы завести в программе строку, можно определить свой строчный тип или использовать стандартный описатель строки. По первому способу:

TYPE

str20 = string[20]; { ввели свой тип - строку из 20 символов }

...

VAR

Result, Error: str20; { отвели место под 2 строки, каждая по 20 символов, задали им имена }

По второму способу:

VAR

Name: string[20]; { создали строку длиной 20 символов с именем Name }

Переменной типа строка можно задавать значения (как и другим типам переменных) тремя различными способами.

 

Во-первых, значение может быть занесено в строку при ее создании. При этом может быть сформирована строка-константа:

CONST

HELLOW = ' Здравствуйте, я - вежливая программа! ';

или строка-переменная с заданным начальным значением:

CONST

Protocol: string[12] = 'RESULT.TXT';

В отличие от первого случая, содержимое строки Protocol в дальнейшем может быть изменено на другое, но не длиннее 12 символов.

 

Во-вторых, переменной типа строка может быть присвоено значение строчного выражения с помощью оператора присваивания:

VAR

St1,St2,St3: string[30];

...

Begin

...

St1:='Пример '; { St1, St2 и St3 получают значения присваиванием }

St2:='строки';

St3:=St1+'новой '+St2; { в St3 окажется 'Пример новой строки' }

 

В-третьих переменная типа строка может быть заполнена операцией ввода:

VAR

St1:string[5];

St2:string;

...

Begin

...

writeln('Введите 1-ю строку');

readln(St1);

{ набираем последовательность символов АБВГДЕЖЗ <Enter> }

writeln('Введите 2-ю строку');

readln(St2);

 

Набираем последовательность символов 'АБВГ ДЕЖЗ" <Enter>, после таких действий переменная St1 будет содержать символы АБВГД, а переменная St2 - 'АБВГ ДЕЖЗ" Текущая длина St1 будет равна 5, St2 - 11.

Из строковых данных можно строить строковые выражения, в которых в качестве операндов выступают строковые константы, переменные строковые функции и символьные данные. В этих выражениях можно применять операцию сцепления двух или более строк (конкатенации), обозначаемую символом '+'. Результатом будет новая строка (длиной не более 255 символов), содержащая первую строку за последним символом которой начинается вторая и так далее.

Для строк определены все 6 операций отношений. Строки сравниваются посимвольно, слева направо, как только встречается в одной строке символ с меньшим кодом, так эта строка признается за меньшую. Отсутствие символа (более короткая строка) при одинаковом начале определяет меньшую строку. Результат операции отношения - логическое значение. Например:

выражение отношения результат вычисления выражения

'A' < 'B' TRUE

'A ' < 'A' FALSE

'ABCD' < 'ACB' TRUE

Если значение строчного выражения превышает по длине максимальную длину переменной, при присваивании произойдет отбрасывание не влезающих (последних, правых) символов.

Как уже упоминалось выше, в выражении могут встречаться символьные переменные. Если символьной переменной присваивается строковое выражение, его значение должно в момент присваивания иметь длину = 1, иначе возникнет ошибка.

К отдельным символам строки можно обращаться по его номеру в строке. Для этого используется индексное выражение:

VAR St1,St2:string[6];

...

Begin

...

St1:='ПРИМЕР';

St2:='Вася';

writeln (St1[4]+St1[3]+St1[6]); оператор печати слова МИР

St1[0]:=St2[0]; теперь строка St содержит слово ПРИМ

writeln('St1[0]=',Ord(St1[0])); так можно распечатать содержимое нулевой ячейки строки St1

Нулевой символ содержит текущую длину строки, его значение формируется автоматически, ему нельзя присваивать значение оператором присваивания (оператор st1[0]:=st2[0] сработает, но контроль длинны не выполнится, и последствия могут быть самыми печальными).

Для работы со строками в Турбо Паскале предусмотрено несколько стандартных процедур и функций, хранящихся в библиотеке с именем System.

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