Упорядоченные структуры информационных объектов


Напоминание:

· информация (для автомата ЭВМ) это-состояние (битовое содержимое) информационного объекта (носителя информации),

· каждый информационный объект имеет уникальное имя (имя собственное, название, адрес в памяти ЭВМ).

Опр. Индексное имя информационного объекта это - название составленное из последовательности символов и натурального числа – собственно индекса.

Пример:

математическая запись индексных имен: а5, Тi

и, аналогичные им, записи на языке Pascal: a[5], T[i].

Системы индексных имен характеризуются «естественной упорядоченностью», т.к. это свойство присуще натуральным числам – обязательной составляющей индексированного имени. Например, имя w5 предшествует имени w7, поскольку индекс (число) 5 меньше индекса (числа) 7.

Опр. Сортировка информации – процесс согласования (установления взаимосвязи) содержимого информационных объектов с их индексными номерами.

Опр. Выборка {ai}, i=1, 2, ...n, называется попарно упорядоченной по операции сравнения P, если для любых двух последовательных объектов ai и ai+1 i=1,2,..,(n-1) выполняется P(ai,ai+1)=true.

Пример: четыре информационных объекта {a1, a2, a3, a4} , содержащие числа {3.5, -2.7, -2.0, 1.1} упорядочены «по убыванию абсолютной величины их значений», т.е. по операции сравнения P(a, b) = |a| > |b|.

8.3. Алгоритм сортировки «поплавок»

1. Проводим последовательное (слева направо) попарное сравнение элементов массива, т.е. вычисляем P(ai,ai+1) для i=1, 2, ...n-1,

2. Если P(ai,ai+1)=false, то меняем содержимое информационных объектов ai и ai+1 местами.

В результате разового просмотра всех пар объектов, что требует выполнения (n-1)-ой операции сравнения, самая «правая» («самая последняя в данной выборке») информация, действительно окажется в самом последнем элементе массива, т.е. в элементе an.

Для упорядочения всей информации выборки, следует повторить пункты (1) и (2) (n-1) раз, причем при каждом очередном повторении количество просматриваемых и сравниваемых объектов сокращается на единицу.

На вопрос о возможном упорядочении информации массива {ai}, i=1, 2, ...n сообразно операции сравнения P(ai, aj) отвечает следующая теорема.

Теорема 1. Выборка {ai}, i=1, 2, ...n может быть попарно отсортирована, если используемая операция сравнения P(ai,aj) антикоммутативна, однако результат сортировки может оказаться неоднозначным.

Теорема 2: Выборка {ai}, i=1, 2, ...n может быть однозначно отсортирована, если используемая операция сравнения P(ai,aj) антикоммутативна и дистрибутивна.

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

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

 



Дата добавления: 2021-12-14; просмотров: 278;


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

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.008 сек.