Информатика (стр. 3 )

Оператор цикла с предусловием:

Оператор цикла с предусловием организует выполнение одного (воз-

можно составного) оператора неизвестное чило раз. Выход из цикла осу-

ществляется, если некоторое логическое выражение окажется ложным. Так

как истинность логического выражения проверяется вначале, тело цикла

может не выполнится ни разу.

Структура оператора.

WHILE <условие> DO <оператор>;

В этой структуре:

<условие> - логическое выражение, истинность которого проверяется

вначале выполнения циклического оператора;

<оператор> - любой выполняемый оператор языка (в том числе и сос-

тавной, т. е. последовательность операторов, заключённая в операторные

скобки BEGIN - END).

Порядок выполнения оператора.

Пока условие истинно выполняется оператор, следующий за служебным

словом DO. Как только условие становится ложно выпонение оператора

цикла прекращается.

Оператор цикла с постусловием организует выполнение цикла, состо-

ящего из любого количества операторов неизвестное заранее количество

раз. Выход из цикла осуществляется, если некоторое логическое выраже-

ние окажется истинным. Так как истинность логического оператора прове-

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

Структура оператора:

REPEAT

<Оператор 1>;

<Оператор 2>;

. . .

<Оператор N>;

UNTIL <условие>;

В этой структуре:

<Оператор 1>; <Оператор 2>; . . . <Оператор N>; - тело цикла.

<условие> - логическое выражение, ложность которого проверяется

после выполнения тела цикла.

Порядок выполнения оператора:

Выполняются операторы, следующие за служебным словом REPEAT. Пос-

ле этого проверяется условие. Если условие ложно, то происходит возв-

рат к выполнению операторов, следующих за служебным словом REPEAT и

снова проверяется условие. Если условие истинно, то выполнение тела

цикла прекращается.

В "жаргонном" переводе на русский язык, оператор цикла с постус-

ловием "звучит" так:

Повторять тело цикла пока не выполнится условие.

В цикле REPEAT тело цикла выполняется по крайней мере один раз.

Оператор цикла с параметром организует выполнение одного операто-

ра заранее известное количество раз.

Структура оператора

Существует два варианта оператора.

Вариант первый:

FOR i := start TO finish DO <оператор>

Вариант второй:

FOR i := start DOWNTO finish DO <оператор>

В этих структурах:

i - параметр цикла;

start - начальное значение параметра;

finish - конечное значение параметра;

<оператор> - тело цикла.

Тип переменной цикла i и значений start и finish должен быть по-

рядковым!

Порядок выполнения оператора:

1. Вычисляются и запоминаются начальное - start, и конечное - finish,

значения параметра цикла. Start и finish могут быть представлены в

виде конкретного значения (в этом случае нет необходимости в вычис-

лениях) или в виде выражения, значение которого вычисляется в нача-

ле выполнения цикла.

2. Параметру цикла i присваивается значение start.

3. Значение параметра цикла i сравнивается со значением finish. Опера-

тор "тело цикла" будет выполнен при выполнении следующего условия:

первый вариант оператора: i <= finish;

второй вариант опеартора: i >= finish.

В противном случае происходит прекращение выполнения циклического

оператора.

4. Параметру цикла присваивается:

первый выриант оператора: следующее большее значение;

второй вариант оператора: следующее меньшее значение.

5. Выполняется пункт 3 данной схемы.

Часто говорят, что первый вариант оператора цикла с параметром, -

цикл с возрастающим параметром; второй вариант, - с убывающим параметром.

Если при первой - же проверке, параметр цикла не будет удовлетворять условий пункта 3, тело цикла не выполнится ни разу.

Телом цикла может быть только один оператор. Для того, чтобы в

теле цикла с параметром выполнить несколько операторов, их необходимо

объединить операторными скобками BEGIN END.

После прекращения выполнения оператора, значение параметра цикла

не определено, за исключением случаев, когда выход из оператора был

осуществлён с помощью GOTO или стандартной процедуры Break.

18 Процедуры и функции в Turbo Pascal`е. Локализация имен.

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

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

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

Формат описания процедуры имеет вид:

procedure имя процедуры (формальные параметры);

раздел описаний процедуры

begin

исполняемая часть процедуры

end;

Формат описания функции:

function имя функции (формальные параметры):тип результата;

раздел описаний функции

begin

исполняемая часть функции

end;

ПРИНЦИП ЛОКАЛИЗАЦИИ суть его состоит в том, что вводимые (описываемые) в какой-либо процедуре программные объекты (метки, константы, переменные, процедуры и функции, используемые для внутри-процедурных потребностей) существуют только в пределах данной процедуры.

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

Глобальные имена хранятся в области памяти, называемой сегментом данных (статическим сегментом) программы. Они создаются на этапе компиляции и действительны на все время работы программы. В отличие от них, локальные переменные хранятся в специальной области памяти, которая называется стек. Они являются временными, так как создаются в момент входа в подпрограмму и уничтожаются при выходе из нее.

19 Локальные и глобальные переменные в Turbo Pascal'e.

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

Указанные трудности в Паскале устраняются благодаря ПРИНЦИПУ ЛОКАЛИЗАЦИИ, суть которого состоит в том, что вводимые (описываемые) в какой-либо процедуре программные объекты (метки, константы, переменные, процедуры и функции, используемые для внутри-процедурных потребностей) существуют только в пределах данной процедуры.

Имена, используемые для описания переменных, констант и других программных объектов внутри подпрограммы, называются ЛОКАЛЬНЫМИ для данной подпрограммы. Программные объекты, описанные в основной программе, называются ГЛОБАЛЬНЫМИ.

Основные правила работы с глобальными и локальными именами можно сформулировать так:

Локальные имена доступны (считаются известными, "видимыми") только внутри того блока, где они описаны. Сам этот блок, и все другие, вложенные в него, называют областью видимости для этих локальных имен.

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

Глобальные имена хранятся в области памяти, называемой сегментом данных (статическим сегментом) программы. Они создаются на этапе компиляции и действительны на все время работы программы. В отличие от них, локальные переменные хранятся в специальной области памяти, которая называется стек. Они являются временными, так как создаются в момент входа в подпрограмму и уничтожаются при выходе из нее.

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

20 Процедуры и функции формальные и фактические параметры в Turbo Pascal`е

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

procedure имя процедуры ( var имя праметра: имя типа );

раздел описаний процедуры

begin

исполняемая часть процедуры

end;

и отделяются друг от друга точкой с запятой. Ключевое слово var может отсутствовать (об этом далее). Если параметры однотипны, то их имена можно перечислять через запятую, указывая общее для них имя типа. При описании параметров можно использовать только стандартные имена типов, либо имена типов, определенные с помощью команды type. Список формальных параметров может отсутствовать.

Вызов процедуры производится оператором, имеющим следующий формат:

имя процедуры(список фактических параметров);

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

Вызов функции в Турбо Паскаль может производиться аналогичным способом, кроме того имеется возможность осуществить вызов внутри какого-либо выражения. В частности имя функции может стоять в правой части оператора присваивания, в разделе условий оператора if и т. д.

Для передачи в вызывающий блок выходного значения функции в исполняемой части функции перед возвратом в вызывающий блок необходимо поместить следующую команду:

имя функции := результат;

При вызове процедур и функций необходимо соблюдать следущие правила:

количество фактических параметров должно совпадать с количеством формальных;

соответствующие фактические и формальные параметры должны совпадать по порядку следования и по типу.

Заметим, что имена формальных и фактических параметров могут совпадать. Это не приводит к проблемам, так как соответствующие им переменные все равно будут различны из-за того, что хранятся в разных областях памяти. Кроме того, все формальные параметры являются временными переменными - они создаются в момент вызова подпрограммы и уничтожаются в момент выхода из нее.

21 Переход в графический режим в Turbo Pascal`е. Масштабирование

Графический режим ПК существенно отличается от текстового как по принципам функционирования, так и по возможностям. Графика применяется практически во всех серьезных программных разработках, так как позволяет увидеть результаты расчетов в виде чертежей, графиков, иллюстраций в движении. Фирмой Borland разработана библиотека графических функций (Модуль Graph. tpu) как приложение к Turbo-пакетам фирмы Borland и графические драйверы - файлы *. bgi (Borland Graphics Interface ), обеспечивающие взаимодействие программ с графическими устройствами.

Подключение графической библиотеки при программировании в среде Turbo-Pascal производится оператором:

Uses Graph;

Переход из текстового режима к графическому (инициализация графики) осуществляется оператором:

InitGraph(Gd, Gm, 'way');

где Gd - имя графического драйвера (параметр-переменная),

Gm - номер графического режима монитора (параметр-переменная),

'way' - дорожка DOS к файлам с графическими драйверами (*. bgi), например, C:\TP7\BGI.

Файлы графических драйверов принято хранить в поддиректории BGI. Если эти файлы располагаются в текущей директории, то дорожку DOS можно не указывать.

В графическом режиме изображение формируется из точек (пикселов) разных цветов. Количество точек на экране и число допустимых цветов можно задавать выбором подключаемого драйвера и номером графического режима. Вариации графических режимов весьма разнообразны, особенно для качественных мониторов. Например, адаптер IBM 8514 / A может обеспечить разрешение 1024 х768 точек и 256 цветов. Однако не все программные продукты рассчитаны на такие режимы.

Приведем таблицу графических возможностей для мониторов EGA, VGA.

Монитор драйвер режим Число точек Число Число видео -

"Gd" "Gm" на экране цветов страниц

EGA EGA 0 640 x

EGA 1 640 x

VGA VGA 0 640 x

VGA 1 640 x

VGA 2 640 x

Обычно драйверы подключаются в режиме автоопределения используемого монитора ПК. Для этого перед инициализацией графики задается Gd:= Detect; или Gd:= 0;. В этом случае по умолчанию устанавливается режим с наибольшим числом точек на экране, а значение параметра "Gm" игнорируется. Номер наибольшего режима для текущего драйвера возвращает функция GetMaxMode;.

Изменить режим можно процедурой SetGraphMode(Gm);

где 0 =<Gm<= GetMaxMode. Экран при этом очищается.

0 X Разрешающую способность для текущего графического

0 GetMaxX; режима можно определить функциями, возвращающими

максимальные значения координат экрана:

GetMaxX; - по оси "Х", GetMaxY; - по оси "Y".

GetMaxY; Начало координат (X= 0, Y= 0) расположено в левом верхнем углу

Y экрана. Ось Х направлена слева направо, ось Y - сверху вниз.

Для возврата из графического режима в текстовый можно использовать операторы:

CloseGraph; - полное прекращение работы графической системы,

RestoreCrtMode; - переключение в текстовый режим с возможностью возврата

к текущим установкам графического режима (без восстановления графического изображения) оператором SetGraphMode; .

22 Процедуры и функции в Turbo Pascal`е Pascal's для работы с экраном в графическом режиме.

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

Функции GetMaxX и GetMaxY.

Возвращают значения типа Word, содержащие максимальные координаты экрана в текущем режиме работы соответственно по горизонтали и вертикали. Например:

Uses Graph;

var

a, b: Integer;

begin

a := Detect; InitGraph(a, b, '');

WriteLn(GetMaxX, GetMaxY:5);

ReadLn;

CloseGraph

end.

Функции GetX и GetY.

Возвращают значения типа Integer, содержащие текущие координаты указателя соответственно по горизонтали и вертикали. Координаты определяются относительно левого верхнего угла окна или, если окно не установлено, экрана.

Процедура SetViewPort.

Устанавливает прямоугольное окно на графическом экране. Заголовок:

Procedure SetViewPort(XI, Y1,X2,Y2: Integer; ClipOn: Boolean);

Здесь X1...Y2 - координаты левого верхнего (XI, Y1) и правого нижнего (X2,Y2) углов окна; СНрОп - выражение типа Boolean, определяющее «отсечку» не умещающихся в окне элементов изображения.

Координаты окна всегда задаются относительно левого верхнего угла экрана. Если параметр ClipOn имеет значение True, элементы изображения, не умещающиеся в пределах окна, отсекаются, в противном случае границы окна игнорируются. Для управления этим параметром можно использовать такие определенные в модуле константы:

const

ClipOn = True; {Включить отсечку}

ClipOff = False; {He включать отсечку}

Процедура GetViewSettings.

Возвращает координаты и признак отсечки текущего графического окна. Заголовок:

Procedure GetViewSettings(var Viewlnfo: ViewPortType);

Здесь Viewlnfo - переменная типа ViewPortType. Этот тип в модуле Graph определен следующим образом:

type

ViewPortType = record

x1,y1,x2,y2: Integer; {Координаты окна}

Clip : Boolean {Признак отсечки}

end ;

Процедура MoveTo.

Устанавливает новое текущее положение указателя. Заголовок:

Procedure MoveTo(X, Y: integer);

Здесь X, Y - новые координаты указателя соответственно по горизонтали и вертикали.

Координаты определяются относительно левого верхнего угла окна или, если окно не установлено, экрана.

Процедура MoveRel.

Устанавливает новое положение указателя в относительных координатах.

Procedure MoveRel(DX, DY: Integer);

Здесь DX. DY- приращения новых координат указателя соответственно по горизонтали и вертикали.

Приращения задаются относительно того положения, которое занимал указатель к моменту обращения к процедуре.

Процедура ClearDevice.

Очищает графический экран. После обращения к процедуре указатель устанавливается в левый верхний угол экрана, а сам экран заполняется цветом фона, заданным процедурой SetBkColor. Заголовок:

Procedure ClearDevice;

Процедура ClearViewPort.

Очищает графическое окно, а если окно не определено к этому моменту - весь экран. При очистке окно заполняется цветом с номером О из текущей палитры. Указатель перемещается в левый верхний угол окна. Заголовок:

Procedure ClearViewPort;

Процедура GetAspectRatio.

Возвращает два числа, позволяющие оценить соотношение сторон экрана. Заголовок:

Procedure GetAspectRatio(var X, Y: Word);

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

GetAspectRatio (Xasp, Yasp);

Rectangle(x1, y1, x1+L*round (Yasp/Xasp), y1+L);

а если L определяет длину квадрата по горизонтали, то используется оператор

Rectangle (x1,y1,x1+L, y1+L*round(Xasp/Yasp));

Процедура SetAspectRatio.

Устанавливает масштабный коэффициент отношения сторон графического экрана. Заголовок:

Procedure SetAspectRatio(X, Y: Word);

Здесь X, Y- устанавливаемые соотношения сторон.

Процедура SetActivePage.

Делает активной указанную страницу видеопамяти. Заголовок:

Procedure SetActivePage(PageNum: Word);

Здесь PageNum - номер страницы.

Процедура может использоваться только с адаптерами, поддерживающими многостраничную работу (EGA, VGA и т. п.). Фактически процедура просто переадресует графический вывод в другую область видеопамяти, однако вывод текстов с помощью Write/WriteLn всегда осуществляется только на страницу, которая является видимой в данный момент (активная страница может быть невидимой). Нумерация страниц начинается с нуля.

Процедура SetVisualPage.

Делает видимой страницу с указанным номером. Обращение:

Procedure SetVisualPAge(PageNum: Word);

Здесь PageNum - номер страницы.

Процедура может использоваться только с адаптерами, поддерживающими многостраничную работу (EGA, VGA и т. п.). Нумерация страниц начинается с нуля.

23 Алгоритмы поиска и выборки элементов из массивов данных.

Двоичный (бинарный) поиск элемента в массиве

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

Переменные Lb и Ub содержат, соответственно, левую и правую границы отрезка массива, где находится нужный нам элемент. Мы начинаем всегда с исследования среднего элемента отрезка. Если искомое значение меньше среднего элемента, мы переходим к поиску в верхней половине отрезка, где все элементы меньше только что проверенного. Другими словами, значением Ub становится (M – 1) и на следующей итерации мы работаем с половиной массива. Таким образом, в результате каждой проверки мы вдвое сужаем область поиска. Так, в нашем примере, после первой итерации область поиска – всего лишь три элемента, после второй остается всего лишь один элемент. Таким образом, если длина массива равна 6, нам достаточно трех итераций, чтобы найти нужное число.

Двоичный поиск - очень мощный метод. Если, например, длина массива равна 1023, после первого сравнения область сужается до 511 элементов, а после второй - до 255. Легко посчитать, что для поиска в массиве из 1023 элементов достаточно 10 сравнений.

Function BinSearch (a:array;Lb, Ub:integer;Key:integer);

Var done:Boolean;

M:integer;

Begin

While not done do

Begin

M:= round((Lb + Ub)/2);

If (key<a[m] then

Ub:=m-1

Else if (key>a[m]) then

Lb:=m+1

Else BinSearch:=m;

If (Lb>Ub) then done:=true;

end;

End;

Интерполяционный поиск элемента в массиве

Представьте себе, что Вы ищете слово в словаре. Маловероятно, что Вы сначала загляните в середину словаря, затем отступите от начала на 1/4 или 3/4 и т. д, как в бинарном поиске.

Если нужное слово начинается с буквы 'А', вы наверное начнете поиск где-то в начале словаря. Когда найдена отправная точка для поиска, ваши дальнейшие действия мало похожи на рассмотренные выше методы.

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

Мы приходим к алгоритму, называемому интерполяционным поиском: Если известно, что К лежит между Kl и Ku, то следующую пробу делаем на расстоянии (u-l)(K-Kl)/(Ku-Kl) от l, предполагая, что ключи являются числами, возрастающими приблизительно в арифметической прогрессии.

Интерполяционный поиск работает за log log N операций, если данные распределены равномерно. Как правило, он используется лишь на очень больших таблицах, причем делается несколько шагов интерполяционного поиска, а затем на малом подмассиве используется бинарный или последовательный варианты.

// Поиск в массиве K[1..N] числа X интерполяционным поиском

find:=false;

FindPos:=-1;

L:=1; u:=N;

while(u>=l)

begin

i=L+(u-L)*(X-K[l])/(K[u]-K[L]);

if(X<K[i]) then u=i-1

else if(X>K[i]) then l=i+1

else begin

find:=true;

FindPos:=I;

End;

24 Алгоритмы сортировки данных. Критерии эффективности работы алгоритма.Сортировка выбором. Сортировка пузырьком. Сортировка простыми вставками. Сортировка Шелла. Сортировка пирамидальная. Сортировка быстрая. Сортировка поразрядная.

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

Критерии Эффективности

Единственного эффективнейшего алгоритма сортировки нет, ввиду множества параметров оценки эффективности:

Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах размера списка (n). Для типичного алгоритма хорошее поведение — это O(n log n) и плохое поведение — это O(n²). Идеальное поведение для упорядочения — O(n). Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей всегда нуждаются по меньшей мере в O(n log n) сравнениях в среднем;

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

Устойчивость (stability) — устойчивая сортировка не меняет взаимного расположения равных элементов.

Естественность поведения — эффективность метода при обработке уже упорядоченных, или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.

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

(Warning! Таблица не проверена. Там где стоят знаки вопроса, значение под сомнением!)

(BrutalScorp-respect for the table)

Вид сортировки	Быстродействие	Память	Устойчивось	Естественность	Краткое описание
Быстрая	O(n*log(n))	требует	неустойчив	естественный	выбираем опорный элемент Ак. Затем эл-ты меньше Ак переносим влево, большие вправо. Затем обе части обрабатываем аналогично
Выбором	O(n^2)	не требует	неустойчив	неестественный	строим массив из "правильных эл-тов" слева-направо. после каждого прохода неотсортированный участок уменьшается
Пузырьком	O(n^2)	не требует	устойчив	Неестественный, (естественный только у модифицир.)	С каждым перебором массива “легкий” эл-т поднимается выше. Производится до тех пор пока не всплывут все
Слиянием	O(n*log(n))	требует	устойчив	Естественный	Разбивка и сортировка сначала по 2 эл-та, затем 4, 8, 16…
Вставками	O(n^2)	не требует	устойчив	Естественный	“просеивание” элемента в отсортированный участок
Шелла	O(n*log(n)) или n^12	?не требует?	неустойчив	?Естественный?	Сортируется сначала каждый 8, затем каждый 4, 2. (разбиваются на пары через 8,4,2)
Поразрядная	O(n*log(n))	требует(?)	устойчив	неестественный	Выстраивание эл-тов по карманам старших разрядов, затем младших

Теперь можно заняться подробным описанием алгоритмов с примерами.