Неділя, 22.12.2024, 14:07
 Вітаю Вас Гость

Група СП-11

Меню сайта
Категории раздела
Міні-чат
500
Наше опитування
Оцініть сайт
Всього відповідей: 13
Статистика

Онлайн всього: 1
Гостей: 1
Користувачів: 0
Головна » Статьи

Всего материалов в каталоге: 2
Показано материалов: 1-2

Реализация класса быстрой сортировки
Статті по С++ | Переглядів: 615 | Додав: mesnuk | Дата: 17.02.2010 | Коментарі (0)

Быстрая сортировка(функция qsort1) очень хорошо справляется с массивом случайных чисел, но если на вход подается уже частично упорядоченная последовательноть либо последовательность содержащая подпоследовательности из одинаковых элементов, расположенных рядом - время выполнения алгоритма значительно возрастает, стремясь к ~ O(n2). В тоже время такой алгоритм как сортировка вставкой - с такими случаями справляется "на ура", сортируя со скоростью ~ O(n). Поэтому используем здесь следующий подход: если в сортируемой последовательности в алгоритме быстрой сортировке остается меньше cutoff элементов - они сортируется сортировкой вставками. cutoff - некоторая константа(которая зависит от начальных условий и обычно равна 3-40).
Подробно:
Статті по алгоритмах | Переглядів: 2477 | Додав: mesnuk | Дата: 17.02.2010 | Коментарі (0)

Форма входу
Пошук
Інше..
Друзі сайту
Лічильник
счетчик посещений