Сортировка выбором

Простая обменная сортировка

Сортировка включением

Пусть имеется массив ключей a[1], a[2], ..., a[n]. Для каждого элемента массива, начиная со второго, производится сравнение с элементами с меньшим индексом (элемент a[i] последовательно сравнивается с элементами a[i-1], a[i-2] ...) и до тех пор, пока для очередного элемента a[j] выполняется соотношение a[j] > a[i], a[i] и a[j] меняются местами.

Если удается встретить такой элемент a[j],

что a[j] <= a[i], или если достигнута нижняя граница массива, производится переход к обработке элемента a[i+1] (пока не будет достигнута верхняя граница массива).

(«методом пузырька")

Для массива a[1], a[2], ..., a[n] работает следующим образом. Начиная с конца массива сравниваются два соседних элемента (a[n] и a[n-1]). Если выполняется условие a[n-1] > a[n], то значения элементов меняются местами. Процесс продолжается для a[n-1] и a[n-2] и т.д., пока не будет произведено сравнение a[2] и a[1].

Понятно, что после этого на месте a[1] окажется элемент массива с наименьшим значением. На втором шаге процесс повторяется, но последними сравниваются a[3] и a[2]. И так далее. На последнем шаге будут сравниваться только текущие значения a[n] и a[n-1]. Аналогия с пузырьком, поскольку наименьшие элементы (самые "легкие") постепенно "всплывают" к верхней границе массива.

При сортировке массива a[1], a[2], ..., a[n] методом простого выбора среди всех элементов находится элемент с наименьшим значением a[i], и a[1] и a[i] обмениваются значениями. Затем этот процесс повторяется для получаемых подмассивов

a[2], a[3], ..., a[n], ... a[j], a[j+1], ..., a[n] до тех пор, пока мы не дойдем до подмассива a[n], содержащего к этому моменту наибольшее значение

Тема 5. Основы информационного моделирования. Реляционная алгебра и ее применение.

Понятие предметной области (ПрО). Объекты как составные элементы ПрО. Виды и свойства объектов. Связи между объектами.

Метод информационного моделирования. Понятие интуитивной и формальной моделей ПрО. База данных как информационная модель ПрО.

Многоуровневая система моделирования ПрО. Проблемно-ориентированные и системно-зависимые модели ПрО.

Способы логико-семантического описания составных элементов ПрО. Типы, экземпляры и ключи информационных объектов. Типы и виды информационных отношений. Граф-модели «объекты-связи». Реляционные (табличные) модели ПрО.

Особенности табличного задания отношений в реляционных базах данных. Понятие об операциях над отношениями.

Теоретико-множественные операции над отношениями. Корректировка баз данных с помощью операций объединения и разности.

Операции проекции, выбора, соединения, деления. Суперпозиция реляционных операций.

Применение реляционной алгебры для обработки отношений в базах данных. Процедурные и декларативные средства обработки отношений.

Среди проблемно-ориентированных моделей предметних областей (ПрО), предназначенных для информационного описания ПрО с точки зрения ее восприятия пользователем, особое место занимает класс информационно-логических (инфологических) моделей ПрО.

Инфологическая модель ПрО – это формализованная модель ПрО, содержащая в себе исчерпывающие сведения о составных элементах ПрО (объектах, их свойствах и взаимосвязях), которые должны быть отображены в информационной базе (ИБ) данной ПрО.

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

Описание составных элементов ПрО языковыми средствами с учетом смыслового содержания слов, называют семантическим (semantikos –смысловой, касающийся смыслового значения слов). Термин«логико-семантический»означает, что в семантическом описании ПрО должна быть отражена логика реальных связей между объектами ПрО, а также логика взаимосвязей между характеристиками (свойствами) этих объектов.

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

· информационные объекты (ИО),

· атрибуты ИО,

· типы и экземпляры ИО,

· ключи ИО,

· информационные отношения-связи (ИОС),

· виды ИОС,

· типы ИОС.

Рассмотрим эти понятия и их использование в качестве средств информационного описания элементного состава ПрО.