Лекция: Алгорнитмы сортировки и их сравнение.
Сортировка – процесс упорядочивания заданного множества объектов. Может быть по возрастанию, убыванию, невозрастанию, неубыванию.
Постановка задачи. Дан массив элементов нужно расположить их в порядке возр. (убыв.). Существует много методов сорт. отлич. степенью эффективности (кол-во сравнений и кол-во обменов). Виды: простой выбор, простого обмена, прямого включения, слияния, Хоара и т.д.
1.Простой выбор: Применяется для массива без повтор. элементов. Суть: 1) Выбрать max эл-т 2) Поменять местами с последним 3) Повторить 1) 2) с оставшимися элементами.
Пример: 1 шаг: 5 4 1 3 2; 2 шаг:2 4 1 3 5; 3 шаг:2 3 1 4 5; 4 шаг:2 1 3 4 5; 5 шаг:1 2 3 4 5.
begin
for i:=n downto 2 do
{цикл по длине рассматриваемой части массива}
begin
{поиск максимального элемента и его номера в текущей части массива}
k:=i; m:=a[i]
{начальные значения максимального элемента и его номера в рассматриваемой части массива}
for j:=2 to i-1 do
if a[j]>m then
begin k:=j; m:=a[k] end
if k<>i then
{перестановка элементов}
begin
a[k]:=a[i];
a[i]:=m
end
end
end;
2.Простой обмен (пузырек): Для любого массива. Суть: просмотр от начала к концу и обмен соседних элементов по принципу i<j a[i]>a[j].
…
var k,i,t:integer;
{k – номер просмотра, i – номер рассмариваемой пары, t – промежуточная переменная для перестановки местами элементов}
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;
3.Прямого включения: Для массива без повтор. элементов. Суть: На k шаге k-1 элемент уже отсортирован, для k ищем место в уже отсортированной части и вставляем его туда.
begin
for k:=2 to n do
begin
x:=a[k]; j:=k-1;
while x³a[j] do
begin
a[j+1]:=a[j];
dec(j);
end;
a[j+1]:=x;
end;
end;
Сравнение по кол-ву сравнений:
1. С – кол-во сравнений. При первом проходе выполняется n-1 сравнений при втором n-2 и т.д. С(мин) = С(мах) = n(n-1)/2
2. Выполняется n-1 просмотров на каждом i просмотре выполняется n-i сравнений. С(мин) = С(мах) = n(n-1)/2
3. Число сравнений на i шаге С(i) самое меньшее =1 (элемент a[i] на своем месте), самое большее i (элемент a[i] меньше всех предыдущих). Среднее (i+1)/2.
С(мин)=n-1 C(max)=(n2+n-2)/2
она работает, тем эффектив. чем ближе массив к отсортиров. В принципе сложность пропрорц. n2
13, .Компьютерное моделирование.
Модель – нек. упрощенное подобие реального объекта. Термины модель и моделирование взаимосвязаны. Моделирование с древн. Времен явл-ся средством познания.
Модель-это образ оригинала, отражающий сущ-нные св-ва, связи и отношения оригинала Исследование модели служит средством для получения нов-х или подтверж. Уже имеющихся сведений об оригинале.(Энциклолпед словарь). Мод-ние-это процесс построения модели и ее исследование
Модель строят в том случае, когда невозм. или затруднит. изучение объекта.