Шейкерне сортування.

Цей алгоритм, по суті, є модифікацією сортування обміном. Відмінність полягає тільки в тому, що якщо в сортуванні обміном проходи здійснювалися тільки в одному напрямі, то тут напрям кожного разу зминюється. В шейкерному сортуванні також можна перевіряти факт перестановки або запам'ятовувати місце останньої перестановки. В базовому алгоритмі кількість подвійних проходів рівно N div 2. Обчислювальна складність шейкерного сортування О(N*N).

6. Метод приєднання.

Ідея даного методу полягає в тому, що кожного разу, маючи вже впорядкований масив з K елементів, ми додаємо ще один елемент, включаючи його в масив так, щоб впорядкованість не порушилася. Сортування може проводитися одночасно з введенням масиву.

Тема. Адреси даних. Вказівники. Динамічна пам’ять .

План

1. Адреси даних. Вказівники.

2. Динамічна пам’ять .

3. Нетипізовані вказівні змінні.

1. Адреси даних. Вказівники.

Розглянемо спрощену схему організації пам'яті. Пам'ять типової машини являє собою масив послідовно пронумерованих або проадресованих осередків, з якими можна працювати окремо або зв'язаними ділянками. Для будь-якого ПК вірні наступні твердження: один байт може зберігати значення типу char, двобайтові комірки можуть розглядатися як ціле типу short, а чотирьохбайтові - як цілі типу long. Вказівник - це група комірок (як правило, двох або чотирьох), в яких може зберігатися адреса. Так, якщо с має тип char, а p - покажчик на с, то ситуація виглядає таким чином:

Унарний оператор & видає адресу об'єкта, так що команда p = &c; присвоює змінній p адресу комірки с (говорять, що p вказує на с). Оператор & застосовується тільки до об'єктів, розташованих в пам'яті: до змінних і елементів масивів. Його операндом не може бути ні вираз, ні константа, ні регістрова змінна.

Унарний оператор * є оператор непрямого доступу. Застосований до вказівника він видає об'єкт, на який даний вказівник вказує.

Змінна – це ділянка пам’яті. Вона має адресу. Щоб визначити адресу змінної використовується оператор визначення адреси &.

Наприклад &a – визначення адреси змінної а.

Адреси комірок пам’яті записується парою чисел (адреса сегмента та зміщення), представлених у 16-вій системі числення.

Наприклад, 8fc0: 0f4e – це два числа 36800 : 3918.

У шістнадцятковій системі числення для пердставлення чисел крім цифр 0..9 використовуються літери латинського алфавіту a, b, c, d, e, f.