Сортировка простым обменом (метод “пузырька”)

Алгоритм: сравниваем последовательно, начиная с первого, соседние элементы и если предыдущий элемент больше последующего, меняем их местами. После первого просмотра самый большой элемент окажется на своем месте - станет последним элементом массива.

Второй просмотр: рассматриваем часть массива с первого до предпоследнего. Очередной самый большой элемент станет предпоследним.

Количество просмотров элементов массива равно N-1. В примере, отмечены цветом те элементы, которые уже стоят на своих местах и в очередном просмотре не участвуют.

Первый просмотр

Исходный массив	8	6	4	2	1
Сравниваем 1 и 2	6	8	4	2	1
Сравниваем 2 и 3	6	4	8	2	1
Сравниваем 3 и 4	6	4	2	8	1
Сравниваем 4 и 5	6	4	2	1	8

 

Второй просмотр

Исходный массив	6	4	2	1	8
Сравниваем 1 и 2	4	6	2	1	8
Сравниваем 2 и 3	4	2	6	1	8
Сравниваем 3 и 4	4	2	1	6	8

 

Третий просмотр

Исходный массив	4	2	1	6	8
Сравниваем 1 и 2	2	4	1	6	8
Сравниваем 2 и 3	2	1	4	6	8

 

Четвертый просмотр (последний)

Исходный массив	2	1	4	6	8
Сравниваем 1 и 2	1	2	4	6	8

 

Реализуем этот алгоритм (N-число элементов массива):

For k:=1 To N-1 Dо

For i:=1 To N-k Do

If A[i]>A[i+1] Then Begin

T:=A[i]; A[i]:=A[i+1]; A[i+1]:=T;

End; {If}

Так как коды символов упорядочены в соответствии английским и русским алфавитом, то этим алгоритмом можно сортировать массивы символов и массивы символьных строк.

Запишем целиком программу с процедурой сортировки массива

Const nmax=100;

Type vector=array[1..nmax] of Integer;

Var a: vector;

   i, n: Integer;

Procedure sort(Var a: vector; n: integer);

Var k, i, T: integer;

Begin

For k:=1 To N-1 Do

   For i:=1 To N-k Do

    If A[i]>A[i+1] Then Begin

        T:=A[i]; A[i]:=A[i+1]; A[i+1]:=t;

     End;

End;

Begin

Write ('Размер массива= '); Readln(n);

Write ('Вводите элементы через пробел или Enter');

For i:=1 to n do Read(a[i]);

sort(a, n);

For i:=1 to n do Write(a[i],' ');

Readln;

Readln;

End.

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

Метод предложен Ч. Э. Р. Хоаром в 1962 году. Быстрая сортировка", хоть и была разработана более 40 лет назад, является наиболее широко применяемым и одним их самых эффективных алгоритмов.

Метод основан на подходе "разделяй - и - властвуй". Общая схема такова:

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

 

Procedure QuickSort(m, t: Integer);

Var i, j, x, w: Integer;

Begin

i:=m; j:=t; x:=A[(m+t) Div 2];

Repeat

While A[i]<x Do Inc(i);

While A[j]>x Do Dec(j);

If i<=j Then Begin

w:=A[i]; A[i]:=A[j]; A[j]:=w;

Inc(i); Dec(j);

End

Until i>j;

If m<j Then QuickSort(m, j);

If i<t Then QuickSort(i, t);

End;

Ниже написана программа, которую вы можете запустить на своем компьютере (сделайте это обязательно!)

 

Const n=10;{размер массива}

Type

list = array[1..n] of integer;

Const

a: list=(9,2,3,7,1,8,5,4,6,10);{заполняем массив числами}

Var   i: integer;

{процедура сортировки}

Procedure QuickSort (m, t: Integer);

{ m и t границы сортируемой части массива }

Var i, j, x, w: Integer;

Begin

i:=m; j:=t; x:=A[(m+t) Div 2];

Repeat

While A[i]<x Do Inc(i);

While A[j]>x Do Dec(j);

If i<=j Then Begin

   w:=A[i]; A[i]:=A[j]; A[j]:=w;

Inc(i); Dec(j);

End

Until i>j;

If m<j Then QuickSort(m, j);

If i<t Then QuickSort(i, t);

End;

{Основная программа}

Begin

  QuickSort (1,n); {указываем весь массив}

for i:=1 to n do Write(a[i],' '); {вывод массива на экран}

Readln;

end.

Поиск данных

Линейный поиск

Задача: поиск в массиве элемента с заданным значением. Последовательно просматриваем элементы массива и сравниваем их значения с искомым значением X.

Например.

For i:=1 To N Do If A[i]=X Then k:=i;

Находится номер (индекс) последнего элемента равного X (последнее вхождение), при этом массив просматривается полностью.

Первое вхождение ищем обратным циклом.

For i:=N DownTo 1 Do If A[i]=X Then k:=i;

Просто, но не эффективно! Возможно, вхождение уже найдено, а цикл просмотра продолжается до конца. Изменим программу.

{первое вхождение}

i:=1;

While (i<=N) And (A[i]<>X) Do Inc(i);{i:=i+1}

If i=N+1 Then Write('X нет в А')

Else Write('номер=', i); 

Обратите внимание на заголовок цикла. Как только элемент будет найден, второе условие станет ложным и цикл завершится. При этом i будет равно или меньше N. Если нужный элемент не будет найден, то, в конце концов, станет ложным первое условие и цикл завершится при i большим N.

В программе предполагается, что если первое условие будет ложным, то второе условие не будет проверяться (уже ясно, что все сложное условие ложно). Поэтому условие (i<=N) стоит первым, в противном случае при i=N+1 возникает ошибка «нарушение границ массива» (при включенном контроле {$R+}). Вообще, при отладке (и только при отладке!) программы настоятельно рекомендуем включать такой контроль. При нарушениях границ массивов можно «испортить» значения других переменных, что сделает работу программы не предсказуемой.

Последнее вхождение будем искать аналогично.

i:=N;

While (i>0) And (A[i]<>X) Do Dec(i);{i:=i-1}

If i=0 Then Then Write('X нет в А')

Else Write('номер=', i); 

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

{не забудьте увеличить размер массива в описании}

{первое вхождение}

i:=1; A[N+1]:=X;

While A[i]<>X Do Inc(i);

If i=N+1 Then Then Write('X нет в А')

Else Write('номер=', i); 

{последнее вхождение - первое с конца}

i:=N; A[0]:=X;

While A[i]<>X Do Dec(i);

If i=0 Then Then Write('X нет в А')

Else Write('номер=', i); 

Очевидно, что число сравнений зависит от места нахождения искомого элемента. В среднем количество сравнений равно (N+1) Div 2, в худшем случае - элемента нет в массиве, N сравнений

Бинарный поиск

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

Отсортированность А позволяет, по результату сравнения со средним элементом массива, исключить из рассмотрения одну из половин. Далее применяем тот же прием по отношение к выбранной половине. Очевидно, не следует начинать поиск, если X>A[n] или X<A[1].

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

 

Const nmax=100;

Type vector=array[1..nmax] of Integer; 

Var a:vector;

i, n: Integer;

X: Integer; {номер максимального элемента}

Function bin(Var A: vector; n, X: integer): integer;

{двоичный поиск X в массиве A, n – размер массива}

Var i, j, m: Integer;

     f: Boolean;

Begin

i:=1; j:=N;

{Ha первом шаге рассматривается весь массив}

f:=False; {Признак того, что X не найден}

While (i<=j) And Not f Do Begin

m:=(i+j) Div 2;

If A[m]=X Then f:=True {Элемент найден}

Else

  If A[m]<X Then i:=m+1 {*Исключаем левую часть}

  Else j:=m-1; {*Правую часть.*}

End;

if f then bin:=m else bin:=0;

End;

Begin{основная программа}

Write ('размер массива='); Readln(n);

Write ('Вводите элементы массива столбиком');

For i:=1 to n do Readln(a[i]);

Write ('искомое число='); Readln(X);

Write(bin(a, n, X));

Readln

End.

Предложим еще одну, рекурсивную, реализацию изучаемого поиска[2]. Значением переменной t является индекс искомого элемента или ноль, если элемент не найден.

Const nmax=100;

Type vector=array[1..nmax] of Integer;

Var a: vector;

i, n, t: Integer;

     X: Integer;

Procedure bin(i, j:Integer; Var t: Integer);

{i и j – диапазон поиска, t результат }

{A и X глобальные переменные}

Var m: Integer;

Begin

If i>j Then t:=0

Else Begin

        m:=(i+j) Div 2;

        If A[m]<X Then bin(m+1, j, t)

        Else

          If A[m]>X Then bin(i, m-1, t)

          Else t:=m;

      End;

End;

Begin {основная программа}

Write ('размер массива='); Readln(n);

Write ('Вводите элементы массива столбиком');

For i:=1 to n do Readln(a[i]);

Write ('искомое число='); Readln(X);

bin(1, n, t); {при первом обращении – весь массив}

Write(t);

Readln

End.

Символьные строки

Общие сведения

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

Описание в программе:

Var S: String;

  R: String[10];

Принципиальным отличием первого описания от второго является то, что при первом случае описания максимальная длина строки составляет 255 символов, а во втором – 10.

Строка в памяти размещается последовательно символ за символом, нулевой байт строки содержит текущую длину строки в символьном типе.

7.2. Стандартные функции для работы со строками:

1. Функция Length (S) – возвращает текущую длину строки.

S:='дом на траве'; L:=Length(S); - L=12

2. Функция Copy (S, k, n) копирует часть S строки из n  символов, начиная k–го символа. Длина строки S не изменяется.

После выполнения операторов

S:='дом на траве'; S1:=Copy(S, 5, 8);

S1 получит значение S1='на траве'

3. Функция Pos (s1, S) – возвращает первое вхождение подстроки в строку.

После выполнения операторов

S:='гиппопотам'; p:=Pos('по', S);

p получит значение p=4. С четвертой позиции начинается первый слог 'по'.

4. Процедура Delete (S, k, n) – удаляет n символов из строки S, начиная с k-го.

После выполнения операторов

S:='на дворе трава, на траве дрова'; Delete(S, 10,16);

S изменится и будет S='на дворе дрова'

5. Процедура Insert (r, S, n) – вставляет r в S с позиции n.

После выполнения операторов

S1:='ике'; S:='на дворе дрова'; Insert(S1, 8);

S изменится и будет S='на дворике дрова'

6. Процедура Str (x[:6:2],S) – преобразует число x в строку S с указанным форматом. Пример ниже поясняет работу функции.

Var k: integer;

  x: real;

Begin

x:=37.289; Str(x:6:2, S); {результат S=' 37.29'}

k:=37; Str(x, S); {результат S='37'}

End.

7. Процедура Val (S, x, Error) – преобразует строку S в число x, если строка S не содержит недопустимых для числа символов, то Error = 0.

Var k: integer;

  x: real;

Begin

S:= '37.289'; Val (S, x, Err); { Err=0}

S:= '37.289';

Val (S, k, Err);

{Err≠0, строка содержит «точку», а k целое}

S:= '37'; Val(S, k, Err); { Err=0}

End.

Сравнение строк

Символы упорядочены по своим кодам так, что 'a' < 'z', 'A' < 'Z', ‘А’ < ‘Я’, ‘а’<’я’. Операции сравнения символов =,<>,<,>,<=,>= - действуют в соответствии со значениями кодов.

Сравнение строк – «лексикографическое», строки сортируются по алфавиту также как фамилии в вашем школьном журнале.

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

 

Const n=100; { максимальное число строк в списке}

Var a: array [1..n] of string[20];

     Fi, Fo: text;

   i, k, j: integer;

          R: string[20];

Begin

{файл Sp.txt должен быть заранее создан}

Assign (Fi, 'Sp.txt'); Reset (Fi);

Assign (Fo, 'NewSp.txt'); Rewrite (Fo);

i:=0; {число строк}

While not Eof(Fi) do Begin {читаем до конца файла}

Inc (i);

Readln(Fi,a[i]);

End;

{получили массив из i строк}

{сортируем массив}

For k:= 1 to (i-1) do

For j:= 1 to (i-k) do

If a[j]>a[j+1] then Begin

   R:=a[j];

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

   a[j+1]:= R;

end;

{пишем строки в файл, пронумеровывая}

For k:=1 to i do Writeln(Fo, k, '. ', a[k]);

Close(Fo); {обязательно закрываем файл}

End.