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