Алгоритмы неустойчивой сортировки

• Сортировка выбором (Selection sort) — Сложность алгоритма: O(n ²); поиск наименьшего или наибольшего элемента и помещение его в начало или конец упорядоченного списка
• Сортировка Шелла (Shell sort) — Сложность алгоритма: O(n log² n); попытка улучшить сортировку вставками
• Пирамидальная сортировка (Сортировка кучи, Heapsort) — Сложность алгоритма: O(n log n); превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка
• Быстрая сортировка (Quicksort), в варианте с минимальными затратами памяти — Сложность алгоритма: O(n log n) — среднее время, O(n ²) — худший случай; широко известен как быстрейший из известных для упорядочения больших случайных списков; с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине. При использовании O(n) дополнительной памяти, можно сделать сортировку устойчивой.

Сортировка пузырьком

template< class T >

void bubbleSort(T* arr, int size)

{

T tmp;

for(int i = 0; i < size - 1; ++i) // i - номер прохода

{

for(int j = 0; j < size - 1; ++j) // внутренний цикл прохода

{

if (arr[j + 1] < arr[j])

{

tmp = arr[j + 1];

arr[j + 1] = arr[j];

arr[j] = tmp;

}

}

}

}

3. Основні елементі об’єктної моделі. Успадкування, множинне успадкування, віртуальне успадкування, абстрактні класи. Приклади об’явлення ієрархії класів.

Абстракция выделяет существенные характеристики некоторого объекта, отличающие его от всех других видов объектов и, таким образом, четко определяет его концептуальные границы с точки зрения наблюдателя

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

Модульность - это свойство системы, которая была разложена на внутренне связные, но слабо связанные между собой модули (Модульность позволяет хранить абстракции раздельно)

Иерархия - это упорядочение абстракций, расположение их по уровням

Насле́дование — механизм объектно-ориентированного программирования (наряду с инкапсуляцией, полиморфизмом и абстракцией), позволяющий описать новыйкласс на основе уже существующего (родительского), при этом свойства и функциональность родительского класса заимствуются новым классом.

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

Дата добавления: 2015-11-16