Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

Алгоритм сортировки вектора методом «пузырек»



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

Пусть дан вектор s[1..n].

Вектор отсортирован по возрастанию, если для любого i=1,...,n-1 выполняется условие s[i]<s[i+1].

Вектор отсортирован по не убыванию, если для любого i=1,...,n-1 выполняется условие s[i]<=s[i+1].

Вектор отсортирован по убыванию, если для любого i=1,...,n-1 выполняется условие s[i]>s[i+1].

Вектор отсортирован по не возрастанию, если для любого i=1,...,n-1 выполняется условие s[i]>=s[i+1].

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

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

Для определенности будем сортировать вектор по не убыванию.

Алгоритм сортировки "пузырек” (bubble-sort)

1. Вектор просматривается слева направо и сравниваются соседние элементы. Если s[i] > s[i+1], то элементы меняются местами.

2. Просмотры продолжаются до тех пор, пока сохраняется неупорядоченность, т.е. находится по крайней мере одна пара, такая что s[i]> s[i+1] для некоторого 1<=i<=n-1.

Просмотр 1.

13 6 8 15 4 13 <-> 6

6 13 8 15 4 13 <-> 8

6 8 13 15 4 15 <-> 4

6 8 13 4 15

Просмотр 2.

6 8 13 4 15 13 <-> 4

6 8 4 13 15

Просмотр 3.

6 8 4 13 15 8 <-> 4

6 4 8 13 15

Просмотр 4.

6 4 8 13 15 6 <-> 4

4 6 8 13 15 Вектор упорядочен!

Сортируется по не убыванию вектор a[1..n].

Sort – переменная, которая получит значение true, когда вектор будет отсортирован.

sort:=false;

while not sort do

begin sort:=true;

for i:=1 TO n-1 do

//Если упорядоченность нарушена, элементы меняются

if a[i]>a[i+1] then

begin sort:=false;h:=a[i];a[i]:=a[i+1];a[i+1]:=h end;

end;//while

Структура данных матрица

Можно объявлять и многомерные массивы, т.е. массивы, элементами которых являются массивы. Например, двумерный массив можно объявить таким образом:

Var A2: array[1..10] of array[1..3] of integer;

Этот оператор описывает двумерный массив, который можно представить себе как таблицу, состоящую из 10 строк и 3 столбцов. То же самое можно объявить более компактно:

Var A2: array[1..10,1..3] of integer;

Обычно используется именно такая форма объявления многомерных массивов. Как и в одномерных массивах, элементы могут иметь любой тип, и индексы тоже могут иметь любой ограниченный тип. Доступ к значениям элементов многомерного массива обеспечивается через индексы, перечисляемые через запятую. Например, А2[4,3] — значение элемента, лежащего на пересечении четвертой строки и третьего столбца.

Функции

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

В общем виде инструкция обращения к функции выглядит так:

Переменная := Функция (Параметры) ;

где: переменная — имя переменной, которой надо присвоить значение, вычисляемое функцией;

Функция — имя функции, значение которой надо присвоить переменной;

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

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

Объявление функции

Объявление функции в общем виде выглядит так:

function Имя (параметр1 : тип1, ..., параметрК : типК) : Тип; var

// здесь объявления локальных переменных begin

// здесь инструкции функции

Имя := Выражение; end;

где:

function — зарезервированное слово языка Delphi, обозначающее, что далее следуют инструкции, реализующие функцию программиста; имя — имя функции. Используется для перехода из программы к инструкциям функции; параметр — это переменная, значение которой используется для вычисления значения функции. Отличие параметра от обычной переменной состоит в том, что он объявляется не в разделе объявления переменных, который начинается словом var, а в заголовке функции. Конкретное значение параметр получает во время работы программы в результате вызова функции из основной программы; тип — тип значения, которое функция возвращает в вызвавшую ее программу.

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

Листинг 6.3. Примеры функций

// проверяет, является ли символ допустимым

// во время ввода целого числа

function Islnt(ch : char) : Boolean;

begin

if (ch >= '0'} and (ch <= '9') // цифры

or (ch = 113) // клавиша <Enter>

or (ch = #8) // клавиша <Backspace>

then Islnt := True // символ допустим

else Islnt := False; // недопустимый символ

end;

// проверяет, является ли символ допустимым

// во время ввода дробного числа

function IsFloat(ch : char; st: string) : Boolean;

begin

if (ch >= '0') and (ch <= '9') // цифры

or (ch = #13) // клавиша <Enter>

or (ch = #8) // клавиша <Backspace>

then

begin

IsFloat := True; // символ верный

Exit; // выход из функции

end;

case ch of

'-': if Length(st) = 0

then IsFloat := True; ',':

if (Pos(',',st) = 0)

and (st[Length(st)]'>= '0') and (st[Length(st)] <= '9')

then // разделитель можно ввести только после цифры // и если он еще

не введен

IsFloat := True; else // остальные символы запрещены

IsFloat := False;

end;

end;

 

 

 




Поиск по сайту:

©2015-2020 studopedya.ru Все права принадлежат авторам размещенных материалов.