https://sp11.ucoz.ua/publ/ Каталог статей Wed, 17 Feb 2010 18:42:39 GMT uCoz Web-Service <STRONG>Реализация класса быстрой сортировки</STRONG> https://sp11.ucoz.ua/publ/statti_po_s/statti_po_s/realizacija_klassa_bystroj_sortirovki/6-1-0-4 Статті по С++ https://sp11.ucoz.ua/publ/statti_po_s/statti_po_s/realizacija_klassa_bystroj_sortirovki/6-1-0-4 Wed, 17 Feb 2010 18:42:39 GMT Быстрая сортировка(функция qsort1) очень хорошо справляется с массивом случайных чисел, но если на вход подается уже частично упорядоченная последовательноть либо последовательность содержащая подпоследовательности из одинаковых элементов, расположенных рядом - время выполнения алгоритма значительно возрастает, стремясь к ~ O(n2). В тоже время такой алгоритм как сортировка вставкой - с такими случаями справляется "на ура", сортируя со скоростью ~ O(n). Поэтому используем здесь следующий подход: если в сортируемой последовательности в алгоритме быстрой сортировке остается меньше cutoff элементов - они сортируется сортировкой вставками. cutoff - некоторая константа(которая зависит от начальных условий и обычно равна 3-40).<BR>Подробно: https://sp11.ucoz.ua/publ/statti_po_algoritmakh/statti_po_algoritmakh/uluchshenie_bystroj_sortirovki_realizacii_c/7-1-0-2 Статті по алгоритмах https://sp11.ucoz.ua/publ/statti_po_algoritmakh/statti_po_algoritmakh/uluchshenie_bystroj_sortirovki_realizacii_c/7-1-0-2 Wed, 17 Feb 2010 18:26:07 GMT