пользователей: 21211
предметов: 10450
вопросов: 177346
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ

Язык программирования Pascal. Составные типы данных. Массивы. Сортировка массивов. Сортировка выбором, сортировка обменом (основная идея, пример реализации). Оценка и характеристики алгоритма сортировки. Примеры других алгоритмов (список, трудоемкость).

 

Паскаль (Pascal) разрабатывался, как учебный язык выского уровня, структурного программирования. Относится к 3-му поколению языков программирования.  На основе ALGOL.

 

Составные типы данных – типы данных базирующиеся на простых. Важна однотипность элементов и способ доступа, позволяющие выделить главные представители сложных типов.

 

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

Массивы могут быть одномерными и многомерными

Описание при помощи слова array в разделе описания типов

Алгоритм сортировки - алгоритм упорядочения элементов в списке

Сортировка массива - процесс перестановки его элементов в опред порядке

Основ требов к методам сортировки - экономия использования памяти

Сортировка выбором (по возраст)

1. Выбираем эл-т с макс знач-ем и меняем его местами с посл.

2. Затем выбираем макс эл-т из оставшихся и меняем на предпосл

3. И т.д. до полной отсортировки

procedure vsortarray(var m:mass; nn:integer);

var i,j,k,max,nm:integer;

 begin

  for i:=1 to nn-1 do

   begin

    max:=m[1]; nm:=1;

    for j:=2 to nn-i+1 do

     if m[j]>max then begin

       max:=m[j];

       nm:=j;

      end;

      k:=m[nm]; m[nm]:=m[nn-i+1]; m[nn-i+1]:=k;

   end; end;

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

(по возраст)1.Сравниваем первые 2 и если 1>2 меняем местами, затем 2 и 3 и т.д.

2. После 1 прохода макс эл-т становится посл.

3. Повторяем 1 операцию

procedure osortarray(var m:mass; nn:integer);

var i,j,k,max,nm:integer;

 begin

  for i:=1 to nn-1 do begin

     for j:=1 to nn-i do

     if m[j]>m[j+1] then begin

       k:=m[j]; m[j]:=m[j+1]; m[j+1]:=k;

       end;end;end;

Алгоритмы сортировки оцениваются по скорости выполнения и эффектив испол памяти

Время - вычисл сложность, основной параметр, характ быстродействие

хорош поведение - n log n; плохое - n^2; идеал - n

Память - ряд алгоритмов требует выделение доп памяти под времен. хранение данных

Характеристики алгоритмов

Устойчивость - постоянство взаимного расположение равных эл-ов

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

Использование операции сравнения

Мин трудоемкость худшего случая - n log n, но они отличаются гибкостью

Сортировка пузырьком - устойчивая, сложность n^2

Сортировка выбором - неустойчивая, сложность n^2

10.


22.01.2015; 17:37
хиты: 36
рейтинг:0
Точные науки
информатика
Языки программирования
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2016. All Rights Reserved. помощь