Метод быстрой сортировки Хоара

Метод быстрой сортировки массива разрботан в 1962 году профессором Оксфордского университета К. Хоаром. Алгоритм состоит в том, чтобы, выбрав некоторый элемент разделяющим, переместить все элементы меньшие (или равные) его левее, а большие – правее. После этого применить тот же ход для левой части и правой части массива, если в этой части больше одного элемента. Алгоритм – рекурсивный, т.е. соответствующая процедура обращается при реализации к самой себе. Сложность алгоритма – O(n*logn) – в среднем. В худшем случае (когда после разделения на каждом шаге один из подмассивов состоит из одного элемента, а второй – из оставшихся) сложность O(n²)

void qsort(int a[], int l, int r)
{
int i = l, j = r, p;
int x = a[(l + r)/2];
while (i <= j)
{

while (a[i] < x)
++i;
while (x < a[j])

--j;

if (i <= j)
{ p = a[i]; a[i] = a[j]; a[j] = p; i++; j--; }

}
if (l < j)
qsort(a, l, j);
if (i < r)
qsort(a, i, r);

}

Рекурсивные функции сортировки

Упорядочить элементы последовательности A=(ai), i=1..n, используя рекурсивную функцию сортировки.
void rec_sort(int *a, int i, int n) // рекурсивной функция сортировки вставками
{ if (i < n)
{ int max_el = a[i], max_ind = i;
for (int j = i; j < n; ++j)
if (a[j] > max_el)
{ max_el = a[j]; max_ind = j;}

if (max_ind > i)
{ a[i] ^= a[max_ind]; a[max_ind] ^= a[i]; a[i] ^= a[max_ind];}
rec_sort(a, i+1, n);
}}

Решение комбинаторных задач: генерация k-элементных подмножеств, генерация перестановок

Генерация k-элементных подмножеств
В комбинаторике такие подмножества называют сочетаниями из n элементов по k элементов и обозначают C_n^k , при программировании гораздо удобнее использовать следующие рекуррентные соотношения

Обычно генерацию всех k-элементных подмножеств проводят в лексикографическом порядке, тем более что в данном случае это не приводит ни к усложнению алгоритма, ни к увеличению его вычислительной трудоемкости. Порядок подмножеств называется лексикографическим, если для любых двух подмножеств справедливо, что ранее должно быть сгенерировано то из них, из индексов элементов которого можно составить меньшее k-значное число в n-ричной системе счисления (или в десятичной, для n < 10). Идея сведения данной задачи к задаче меньшей размерности следующая. Первым элементом подмножества может быть любой элемент, начиная с первого и заканчивая (n – k + 1)-м элементом. После того, как индекс первого элемента подмножества зафиксирован, осталось выбрать k – 1 элемент из элементов с индексами, большими, чем у первого. Далее поступаем аналогично. Когда выбран последний элемент, то мы достигли конечного уровня рекурсии и выбранное подмножество можно обработать.

Классическая архитектура компьютера

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

Принципы построения компьютеров (принципы фон Неймана):

1.Принцип программного управления.
2. Принцип однородности памяти.
3. Принцип адресности.

Основные компоненты архитектуры персонального компьютера:

Процессор Внутренняя (основная) память Внешняя память

Устройство ввода Устройство вывода

Внутренняя память обладает 2^мя основными свойствами: дискретность, адресуемость. Поле памяти, с которым может работать команда, характеризуется адресом(числовое значение, определяющее местоположение поля в памяти) и содержимым(числовое значение, хранящееся в этом поле).

Процессор - программно-управляемое устройство

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

Команды процессора.

Каждая команда представляют собой последовательность двоичных разрядов и содержит:
код операции, который надо выполнить по данной команде,

информацию об операндах,
информацию о результате.
Операнд – элемент информации, участвующей в выполняемой операции.

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

1) Извлечение из основной памяти команды, адрес которой находится в счетчике команд.
2) Расшифровка.
3) При необходимости операнды извлекаются из памяти.
4) Выполнение операции с кодом, заложенным в данной команде (если результат операции не надо помещать в память, то процессор переходит к действию 6)
5) Сохранение результата в памяти.
6) Вычисление адреса следующей команды и запоминание его в счётчике команд. Переход к действию 1