ПОЗНАВАТЕЛЬНОЕ

Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.

Отёска стен и прирубка косяков - Когда на доме не достаёт окон и дверей, красивое высокое крыльцо ещё только в воображении, приходится подниматься с улицы в дом по трапу.

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

Stdio.h: Функции ввода-вывода на консоли и файл.

...

catch (<объявление исключения>) { <операторы> }

Условный оператор: if (<выражение>) <оператор 1> [else <оператор 2>]

Оператор-переключатель:
switch (<выражение>)
{
case <константное выражение 1>: <операторы 1>
case <константное выражение 2>: <операторы 2>
...
case <константное выражение N>: <операторы N>
[default: <операторы>]
}

Оператор-переключатель предназначен для выбора одного из нескольких альтернативных путей выполнения программы. Вычисление оператора-переключателя начинается с вычисления выражения, после чего управление передается оператору, помеченному константным выражением, равным вычисленному значению выражения. Выход из оператора-переключателя осуществляется оператором break. Если значение выражения не равно ни одному константному выражению, то управление передается оператору, помеченному ключевым словом default, если он есть.

Оператор цикла с предусловием: while (<выражение>) <оператор>
Оператор цикла с постусловием: do <оператор> while <выражение>;

В языке C++ этот оператор отличается от классической реализации цикла с постусловием тем, что при истинности выражения происходит продолжение работы цикла, а не выход из цикла.

Оператор пошагового цикла:
for ([<начальное выражение>];
[<условное выражение>];
[<выражение приращения>])
<оператор>

Тело оператора for выполняется до тех пор, пока условное выражение не станет ложным (равным 0). Начальное выражение и выражение приращения обычно используются для инициализации и модификации параметров цикла и других значений. Начальное выражение вычисляется один раз до первой проверки условного выражения, а выражение приращения вычисляется после каждого выполненияоператора. Любое из трех выражений заголовка цикла, и даже все три могут быть опущены (не забывайте только оставлять точки с запятой). Если опущено условное выражение, то оно считается истинным, и цикл становится бесконечным.

Оператор пошагового цикла в языке С++ является гибкой и удобной конструкцией, поэтому оператор цикла с предусловием while используется в языке С++ крайне редко, т.к. в большинстве случаев удобнее пользоваться оператором for.

Оператор разрыва: break;

Оператор разрыва прерывает выполнение операторов while, do, for и switch. Он может содержаться только в теле этих операторов. Управление передается оператору программы, следующему за прерванным. Если оператор разрыва записан внутри вложенных операторов while, do, for, switch, то он завершает только непосредственно охватывающий его оператор.

Оператор продолжения: сontinue;

Оператор продолжения передает управление на следующую итерацию в операторах цикла while, do, for. Он может содержаться только в теле этих операторов. В операторах do и while следующая итерация начинается с вычисления условного выражения. В операторе for следующая итерация начинается с вычисления выражения приращения, а затем происходит вычисление условного выражения.

Оператор возврата: return [<выражение>];

Оператора возврата заканчивает выполнение функции, в которой он содержится, и возвращает управление в вызывающую функцию. Управление передается в точку вызывающей функции, непосредственно следующую за оператором вызова. Значение выражения, если она задано, вычисляется, приводится к типу, объявленному для функции, содержащей оператор возврата, и возвращается в вызывающую функцию. Если выражение опущено, то возвращаемое функцией значение не определено.

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

4) Заголовки, подключение библиотек, стандартные библиотеки ввода-вывода, математические операции.
б) Подключение библиотек:
Чтобы подключить библиотеку к программе на языке C или C++, нужно выполнить два действия:

Включить в исходный текст заголовочные файлы библиотеки (.h или .hpp) директивой #include
Обеспечить, чтобы при сборке программы использовались соответствующие объектные файлы библиотеки (в зависимости от системы они могут иметь расширения .lib, .a, .o, .obj и т.д.) В зависимости от используемого компилятора это делается разными способами, например:
– добавить файл(ы) в проект как объектные;
– в MS Visual Studio: добавить имя файла в Linker->Input->Additional Dependencies (если файл в другом каталоге, путь добавить в Linker->General->Additional Library Directories);
– при использовании make прописать файл в список файлов для линкера (обычно это LIBS= или т.п.).
А если библиотека представлена в исходных текстах, надо просто добавить все нужные .c (.cpp) файлы в проект программы.

в) Стандартные библиотеки:
<algorithm> Различные операции на контейнерах (STL)

<bitset> Битовые множества (STL)

<complex> Комплексные числа

<deque> Двухсторонние очереди (STL)

<exception> Обработка исключительных ситуаций

<fstrearn> Работа с файловыми потоками для чтения и записи в один и тот же файл

<functional> Различные объекты-функции (STL)

<iomanip> Манипуляторы ввода-вывода

<ios> Классы ввода-вывода нижнего уровня

<iosfwd> Упреждающие объявления для систем ввода-вывода

<iostream> Стандартные классы ввода-вывода

<istream> Обработка входных потоков

<iterator> Доступ к содержимому контейнеров (STL)

<limits> Различные ограничения реализации

<list> Линейные списки (STL)

<locale> Информация, связанная с традициями конкретных стран или географических регионов

<map> Отображения (ключи и значения) (STL)

<memory> Распределение памяти с помощью распределителей памяти (STL)

<new> Выделение памяти с помощью оператора new

<numeriс> Универсальные операции над числами

<ostream> Обработка выходных потоков

<queue> Очереди (STL)

<set> Множества (STL)

<sstream> Обработка строковых потоков

<stack> Стеки(SLT)

<stdexcept> Стандартные исключительные ситуации

<streambuf> Буферизированная обработка потоков

<string> Стандартный класс string (STL)

<typeinfo> Динамическая информация о типе

<utility> Шаблоны общего назначения (STL)

<valarray> Операции над массивами, содержащими значения

<vector> Векторы (динамические массивы) (STL)
г) Математические операции:

Функция	Описание	Пример
abs( a )	модуль или абсолютное значение от а	abs(-3.0)= 3.0 abs(5.0)= 5.0
sqrt(a)	корень квадратный из а,причём ане отрицательно	sqrt(9.0)=3.0
pow(a, b)	возведение ав степень b	pow(2,3)=8
ceil( a )	округление а до наименьшего целого, но не меньше чем а	ceil(2.3)=3.0 ceil(-2.3)=-2.0
floor(a)	округление а до наибольшего целого, но не больше чем а	floor(12.4)=12 floor(-2.9)=-3
fmod(a, b)	вычисление остатка от a/b	fmod(4.4, 7.5) = 4.4 fmod( 7.5, 4.4) = 3.1
exp(a)	вычисление экспоненты е^а	exp(0)=1
sin(a)	a задаётся в радианах
cos(a)	a задаётся в радианах
log(a)	натуральный логарифм a(основанием является экспонента)	log(1.0)=0.0
log10(a)	десятичный логарифм а	Log10(10)=1

5) Циклы, операторы прерывания.
a) Цикл for:Если мы знаем точное количество действий (итераций) цикла, то можем использовать цикл for. Синтаксис его выглядит примерно так:

for (действие до начала цикла;
условие продолжения цикла;
действия в конце каждой итерации цикла)
{
инструкция цикла;
инструкция цикла 2;
инструкция цикла N;
}

Итерацией цикла называется один проход этого цикла. Существует частный случай этой записи, который мы сегодня и разберем:

for (счетчик = значение; счетчик < значение; шаг цикла)
{
тело цикла;
}

Счетчик цикла — это переменная, в которой хранится количество проходов данного цикла.
б) Цикл while:Когда мы не знаем, сколько итераций должен произвести цикл, нам понадобится цикл while или do...while. Синтаксис цикла while в C++ выглядит следующим образом.

while (Условие)
{
Тело цикла;
}

Данный цикл будет выполняться, пока условие, указанное в круглых скобках является истиной. Решим ту же задачу с помощью цикла while. Хотя здесь мы точно знаем, сколько итераций должен выполнить цикл, очень часто бывают ситуации, когда это значение неизвестно.
в) Цикл do while очень похож на цикл while. Единственное их различие в том, что при выполнении цикла do while один проход цикла будет выполнен независимо от условия.
Оператор прерывания цикла необходим для того, чтобы закончить цикл в любом операторе тела цикла. Для С++ - break.

6) Условный оператор. Особенности значений выражения условного оператора. Составной оператор.
а) Условный оператор: if (<выражение>) <оператор 1> [else <оператор 2>]
б) Составной оператор: {...}Действие составного оператора состоит в последовательном выполнении содержащихся в нем операторов, за исключением тех случаев, когда какой-либо оператор явно передает управление в другое место программы.

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

8) Макросы и функции.
а) Макросы - это препроцессорные "функции" , т.е. лексемы, созданные с помощью директивы #define, которые принимают параметры подобно функциям. После директивы #define указывается имя макроса, за которым в скобках (без пробелов) параметры, отделенные запятыми и определение макроса, отделенное пробелом. Параметры макросов лучше писать в скобках, хотя это не обязательно, но иногда отсутствие скобок приводит к неожиданным результатам.
#define MACRO1(x) x * x
#define MACRO2(x) ( x ) * ( x )
int a =2;
int b=3;
cout

результат:
macro 1- 11
macro 2- 25

б) Фу́нкция в программировании — поименованный фрагмент программного кода (подпрограмма), к которому можно обратиться из другого места программы. С именем функции неразрывно связан адрес первой инструкции (оператора), входящей в функцию, которой передаётся управление при обращении к функции. После выполнения функции, управление возвращается обратно в адрес возврата — точку программы, где данная функция была вызвана.
void name(std::string text)
{
std::cout << text;
}

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

10) Указатели, ссылки. Операторы *, &.
Указатель (англ. pointer) — переменная, диапазон значений которой состоит из адресов ячеек памяти или специального значения — нулевого адреса. Последнее используется для указания того, что в данный момент указатель не ссылается ни на одну из допустимых ячеек.
В языке программирования C++ ссылка — это простой ссылочный тип, менее мощный, но более безопасный, чем указатель, унаследованный от языка Си. Название C++ ссылка может приводить к путанице, так как в информатике под ссылкой понимается обобщенный концептуальный тип, а указатели и С++ ссылки являются специфическими реализациями ссылочного типа.

11) Массивы. Особенности доступа к элементам массива.
Массив - это структура данных, представленная в виде группы ячеек одного типа, объединенных под одним единым именем. Массивы используются для обработки большого количества однотипных данных. Имя массива является указателем. Отдельная ячейка данных массива называется элементом массива. Элементами массива могут быть данные любого типа. Массивы могут иметь как одно, так и более одного измерений. В зависимости от количества измерений массивы делятся на одномерные массивы, двумерные массивы, трёхмерные массивы и так далее до n-мерного массива. Чаще всего в программировании используются одномерные и двумерные массивы.

12) Динамическое выделение памяти.

13) Рекурсия. Рекурсивные функции. Пример использования.
В программированиирекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция вызывает функцию , а функция — функцию . Количество вложенных вызовов функции или процедуры называется глубиной рекурсии. Рекурсивная программа позволяет описать повторяющееся или даже потенциально бесконечное вычисление, причём без явных повторений частей программы и использования циклов. Структурно рекурсивная функция на верхнем уровне всегда представляет собой команду ветвления (выбор одной из двух или более альтернатив в зависимости от условия (условий), которое в данном случае уместно назвать «условием прекращения рекурсии»), имеющей две или более альтернативные ветви, из которых хотя бы одна является рекурсивной и хотя бы одна — терминальной. Рекурсивная ветвь выполняется, когда условие прекращения рекурсии ложно, и содержит хотя бы один рекурсивный вызов — прямой или опосредованный вызов функцией самой себя. Терминальная ветвь выполняется, когда условие прекращения рекурсии истинно; она возвращает некоторое значение, не выполняя рекурсивного вызова. Правильно написанная рекурсивная функция должна гарантировать, что через конечное число рекурсивных вызовов будет достигнуто выполнение условия прекращения рекурсии, в результате чего цепочка последовательных рекурсивных вызовов прервётся и выполнится возврат. Помимо функций, выполняющих один рекурсивный вызов в каждой рекурсивной ветви, бывают случаи «параллельной рекурсии», когда на одной рекурсивной ветви делается два или более рекурсивных вызова. Параллельная рекурсия типична при обработке сложных структур данных, таких как деревья. Простейший пример параллельно-рекурсивной функции — вычисление ряда Фибоначчи, где для получения значения n-го члена необходимо вычислить (n-1)-й и (n-2)-й. Реализация рекурсивных вызовов функций в практически применяемых языках и средах программирования, как правило, опирается на механизм стека вызовов — адрес возврата и локальные переменные функции записываются в стек, благодаря чему каждый следующий рекурсивный вызов этой функции пользуется своим набором локальных переменных и за счёт этого работает корректно. Оборотной стороной этого довольно простого по структуре механизма является то, что на каждый рекурсивный вызов требуется некоторое количество оперативной памяти компьютера, и при чрезмерно большой глубине рекурсии может наступить переполнение стека вызовов. Вопрос о желательности использования рекурсивных функций в программировании неоднозначен: с одной стороны, рекурсивная форма может быть структурно проще и нагляднее, в особенности, когда сам реализуемый алгоритм по сути рекурсивен. Кроме того, в некоторых декларативных или чисто функциональных языках (таких как Пролог или Haskell) просто нет синтаксических средств для организации циклов, и рекурсия в них — единственный доступный механизм организации повторяющихся вычислений. С другой стороны, обычно рекомендуется избегать рекурсивных программ, которые приводят (или в некоторых условиях могут приводить) к слишком большой глубине рекурсии. Так, широко распространённый в учебной литературе пример рекурсивного вычисления факториала является, скорее, примером того, как не надо применять рекурсию, так как приводит к достаточно большой глубине рекурсии и имеет очевидную реализацию в виде обычного циклического алгоритма. Имеется специальный тип рекурсии, называемый «хвостовой рекурсией» (структура рекурсивного алгоритма такова, что рекурсивный вызов является последней выполняемой операцией в функции, а его результат непосредственно возвращается в качестве результата функции). Интерпретаторы и компиляторы функциональных языков программирования, поддерживающие оптимизацию кода (исходного или исполняемого), автоматически преобразуют хвостовую рекурсию к итерации, благодаря чему обеспечивается выполнение алгоритмов с хвостовой рекурсией в ограниченном объёме памяти. Такие рекурсивные вычисления, даже если они формально бесконечны (например, когда с помощью рекурсии организуется работа командного интерпретатора, принимающего команды пользователя), никогда не приводят к исчерпанию памяти. Однако далеко не всегда стандарты языков программирования чётко определяют, каким именно условиям должна удовлетворять рекурсивная функция, чтобы транслятор гарантированно преобразовал её в итерацию. Одно из редких исключений — язык Scheme (диалект языка Lisp), описание которого содержит все необходимые сведения. Теоретически, любую рекурсивную функцию можно заменить циклом и стеком. Однако такая модификация, как правило, бессмысленна, так как приводит лишь к замене автоматического сохранения контекста в стеке вызовов на ручное выполнение тех же операций с тем же расходом памяти. Исключением может быть ситуация, когда рекурсивный алгоритм приходится моделировать на языке, в котором рекурсия запрещена.

Stdio.h: Функции ввода-вывода на консоли и файл.

15) Stdio.h: Форматированный ввод-вывод.

16) Поразрядные (побитовые) операции.
Информация в компьютере представляется в двоичной системе (наличие и отсутствие напряжения). Минимальной единицей информации является бит – ноль или единица, ложь или истина, «нет» или «да». Каждый байт состоит из 8 бит. Если число знаковое (signed), то самый левый его бит обозначает знак числа – 0 для положительных чисел и 1 для отрицательных чисел, остальные биты формируют модуль числа (это относится только к целым числам, вещественные числа всегда со знаком). Если число беззнаковое (unsigned), то все биты участвуют в формировании значения, но число может быть только положительным. Положительные целые числа в компьютере представляются в нормальном коде – это обычное представление числа в двоичной системе, а отрицательные – в дополнительном коде. Для получения дополнительного кода берется двоичное представление равного по модулю целого числа, затем все цифры двоичного представления инвертируются (0 переходит в 1, 1 – в 0), при этом получается так называемый обратный код, к которому прибавляется 1 для получения дополнительного кода. Например, нормальный код числа 207 при использовании 2 байт – 0000000011001111, а дополнительный код числа -207 – 1111111100110001 (количество цифр в числе существенно!). Если сложить два эти числа, получается 0 (с переносом 1 за старший разряд числа). При сложении различных по модулю положительного и отрицательного чисел получается число в нормальном коде, если результат больше 0, и число в дополнительном коде, если результат меньше 0. Существуют операции, которые работают с битами – можно взять отрицание, применить операции «И» или «ИЛИ». Поразрядные операции применяются к перечислениям и интегральным типами – bool,char, short, int и long (возможно, с модификатором unsigned). Однако нельзя применить эти операции к одному биту, а можно лишь применить одну и ту же операцию ко всем битам переменной.
a) Операции «отрицание» ~, «и» &, «или» |, «исключающее или» ^.
б) Операции сдвига.
Операции сдвига вправо и сдвига влево сдвигают биты в переменной на заданное количество позиций. Существует три разновидности сдвига:

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

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

17) Структуры. Выравнивание структур.
В языке Си, структура (struct) — композитный тип данных, инкапсулирующий без сокрытия набор значений различных типов. Порядок размещения значений в памяти задаётся при определении типа и сохраняется на протяжении времени жизни объектов, что даёт возможность косвенного доступа (например, через указатели). Пример объявления структуры:

struct str_name

{

int member_1;

float member_2;

char member_3[256];

/* ... */

};

// объявление структуры

struct str_name struct0;

// объявление и инициализация структуры

struct str_name struct1 = {1, 3.1416f, "doit" /* ... */};

// объявление структуры и поимённая инициализация полей

// поддерживается стандартом, начиная с C99

struct str_name struct3 = {.member_1=2, .member_2=3.1416f, .member_3="doit" /* ... */};
б) Выравнивание структур: Если требуется сделать иное выравнивание в структуре, необходимо использовать вспомогательные члены-"заполнители" нужных размеров. Пример:

struct trade_settings

{

uchar slippage; // значение допустимого проскальзывания -размер 1 байт

char reserved1; // 1 байт пропуска

short reserved2; // 2 байта пропуска

int reserved4; // еще 4 байта пропуска. Обеспечили выравнивание на границу 8 байт

double take; // значения цены фиксации прибыли

double stop; // значение цены защитного стопа

};

Такое описание выровненных структур необходимо только для передачи в импортированные dll-функции.

18) Структуры. Варианты использования структур. Копирование структур.
а) Структура(struct) — композитный тип данных, инкапсулирующий без сокрытия набор значений различных типов. Порядок размещения значений в памяти задаётся при определении типа и сохраняется на протяжении времени жизни объектов, что даёт возможность косвенного доступа (например, через указатели).
struct str_name

{

int member_1;

float member_2;

char member_3[256];

/* ... */

};

// объявление структуры

struct str_name struct0;

// объявление и инициализация структуры

struct str_name struct1 = {1, 3.1416f, "doit" /* ... */};

// объявление структуры и поимённая инициализация полей

// поддерживается стандартом, начиная с C99

struct str_name struct3 = {.member_1=2, .member_2=3.1416f, .member_3="doit" /* ... */};

19) Сортировка массива Вставками.
Сортировка вставками (англ. Insertion sort) — алгоритм сортировки, в котором элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов. Вычислительная сложность - . На вход алгоритма подаётся последовательность чисел: . Сортируемые числа также называют ключами. Входная последовательность на практике представляется в виде массива с элементами. На выходе алгоритм должен вернуть перестановку исходной последовательности , чтобы выполнялось следующее соотношение . В начальный момент отсортированная последовательность пуста. На каждом шаге алгоритма выбирается один из элементов входных данных и помещается на нужную позицию в уже отсортированной последовательности до тех пор, пока набор входных данных не будет исчерпан. В любой момент времени в отсортированной последовательности элементы удовлетворяют требованиям к выходным данным алгоритма. Данный алгоритм можно ускорить при помощи использования бинарного поиска для нахождения места текущему элементу в отсортированной части. Проблема с долгим сдвигом массива вправо решается при помощи смены указателей.

20) Сортировка массива Пузырьком.
Сортировка простыми обменами, сортиро́вка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: . Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяются более эффективные алгоритмы сортировки. В то же время метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как шейкерная сортировка, пирамидальная сортировка и быстрая сортировка. Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма).
void bubble_sort(int *a, int length) {

for (int j = 0; j < length-1; j++) {

for (int i = 0; i < length - j - 1; i++) {

if (a[i] > a[i+1]) {

int b = a[i]; //change for elements

a[i] = a[i+1];

a[i+1] = b;

}

21) Сортировка массива Шейкера.
Сортировка перемешиванием (англ. Cocktail sort) — разновидность пузырьковой сортировки. Анализируя метод пузырьковой сортировки, можно отметить два обстоятельства.
Во-первых, если при движении по части массива перестановки не происходят, то эта часть массива уже отсортирована и, следовательно, ее можно исключить из рассмотрения.
Во-вторых, при движении от конца массива к началу минимальный элемент “всплывает” на первую позицию, а максимальный элемент сдвигается только на одну позицию вправо.
Эти две идеи приводят к следующим модификациям в методе пузырьковой сортировки. Границы рабочей части массива (т.е. части массива, где происходит движение) устанавливаются в месте последнего обмена на каждой итерации. Массив просматривается поочередно справа налево и слева направо.
#include <cstddef>

#include <utility>

template<typename T>

void shaker_sort(T array[], std::size_t size)

{

for (std::size_t left_idx = 0, right_idx = size - 1;

left_idx < right_idx;)

{

for (std::size_t idx = left_idx; idx < right_idx; idx++)

{

if (array[idx + 1] < array[idx])

{

std::swap(array[idx], array[idx + 1]);

}

right_idx--;

for (std::size_t idx = right_idx; idx > left_idx; idx--)

{

if (array[idx - 1] > array[idx])

{

std::swap(array[idx - 1], array[idx]);

}

left_idx++;

}

22) Сортировка массива Гномья.
Гномья сортировка (англ. Gnome sort) — алгоритм сортировки, похожий на сортировку вставками, но в отличие от последней перед вставкой на нужное место происходит серия обменов, как в сортировке пузырьком.
template<class T> void GnomeSort(T *A, int N) {

int i = 0;

while(i < N) {

if(i == 0 || A[i - 1] <= A[i]) ++ i;

else {

T Temp = A[i];

A[i] = A[i - 1];

A[i - 1] = Temp;

-- i;

}

23) Сортировка массива Шелла.
Сортировка Шелла (англ. Shell sort) — алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами — это сортировка вставками с предварительными «грубыми» проходами. Аналогичный метод усовершенствования пузырьковой сортировки называется сортировка расчёской. При сортировке Шелла сначала сравниваются и сортируются между собой значения, стоящие один от другого на некотором расстоянии (о выборе значения см. ниже). После этого процедура повторяется для некоторых меньших значений , а завершается сортировка Шелла упорядочиванием элементов при (то есть обычной сортировкой вставками). Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки, например, пузырьковой, каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, а при сортировке Шелла это число может быть больше). Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:

отсутствие потребности в памяти под стек;
отсутствие деградации при неудачных наборах данных — быстрая сортировка легко деградирует до O(n²), что хуже, чем худшее гарантированное время для сортировки Шелла.

template< typename RandomAccessIterator, typename Compare >

void shell_sort( RandomAccessIterator first, RandomAccessIterator last, Compare comp )

{

for( typename std::iterator_traits< RandomAccessIterator >::difference_type d = ( last - first ) / 2; d != 0; d /= 2 )

for( RandomAccessIterator i = first + d; i != last; ++i )

for( RandomAccessIterator j = i; j - first >= d && comp( *j, *( j - d ) ); j -= d )

std::swap( *j, *( j - d ) );

}

24) Сортировка массива Рассческой.
Сортировка расчёской (англ. comb sort) — это довольно упрощённый алгоритм сортировки. Сортировка расчёской улучшает сортировку пузырьком, и конкурирует с алгоритмами, подобными быстрой сортировке. Основная идея — устранить черепах, или маленькие значения в конце списка, которые крайне замедляют сортировку пузырьком (кролики, большие значения в начале списка, не представляют проблемы для сортировки пузырьком).
template <typename T, typename Comp>

void combsort(T array[ ], std::size_t size, Comp cmp) {

if (array && size) {

std::size_t jump = size;

bool swapped = true;

while (jump > 1 || swapped) {

if (jump > 1)

jump /= 1.24733;

swapped = false;

for (std::size_t i = 0; i + jump < size; ++i)

if (cmp(array[i + jump], array[i])) {

std::swap(array[i], array[i + jump]);

swapped = true;

}