Здравствуйте, Vamp, Вы писали:
CC>>Когда надо досортировать почти отсортированные данные. CC>>У нас применяется в проекте — по результатам тестов замена std::sort на рукописный бабл дала заметный прирост. V>На первый взгляд не очевидно — бабл как делал n сравнений на каждый проход, так и делает. От того, что массив уже отсортирован, вроде ничего изменяться не должно... если только операция собственно копирования значений не слишком долгая.
quick sort — далеко не всегда идеальный вариант. Другой пример его медленной работы — сортировка массива состоящего из больших отсортированных кусков. Смотрите внимательней на его алгоритм.
Хотя за использование bubble sort я бы всё-таки уволил (может и не уволил бы, но за нежелание помимо quicksort'a и бабла вспомнить какой-нибудь ещё алгоритм наказать следует).
Для маленьких массивов можно применять insertion sort (развитие бабла), для тех что покрупнее — либо сортировать quick sort'ом наоборот (то есть именить функцию сравнения на обратную), либо использовать какой-то другой алгоритм. Либо вообще всегда использовать алгоритмы с фиксированной сложностью, например — heapsort.
Когда я имел дело с данными в несколько миллионов елементов, простой quick sort проседал на полтора часа (а может полчаса, точно не помню, но очень на много); heapsort ~ 20 секунд. Переделанный quicksort ~15 секунд.
