Форум программистов, компьютерный форум CyberForum.ru

QUICKsort и MERGEsort недостатки и преимущества - C++

Восстановить пароль Регистрация
 
ferc
2 / 2 / 1
Регистрация: 20.02.2014
Сообщений: 29
06.03.2014, 19:37     QUICKsort и MERGEsort недостатки и преимущества #1
Добрый вечер!
Qsort плоха тем, что в худшем случае работает за О(n^2). Mergesort стабильна и работает ВСЕГДА за n*log(n).
Расскажите, пожалуйста, поподробнее, в чем преимущество quicksort? Чем она лучше mergesort?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.03.2014, 19:37     QUICKsort и MERGEsort недостатки и преимущества
Посмотрите здесь:

проверте где ошибка в mergeSort C++
C++ Число перестановок QuickSort
stdlib.h - quicksort C++
C++ QuickSort
QuickSort найдите ошибку C++
C++ Прокомментировать код. QuickSort
Преимущества и недостатки при реализации стека, очереди и дека через дин. массива C++
Не работает сортировка (MergeSort) C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
DrOffset
6422 / 3796 / 878
Регистрация: 30.01.2014
Сообщений: 6,585
06.03.2014, 20:25     QUICKsort и MERGEsort недостатки и преимущества #2
у quicksort есть практические достоинства:
1) хорошо распараллеливается
2) обладает более высокой локальностью, на каком-то уровне рекурсии кусок может быть полностью закеширован, а это значительно ускорит процесс
3) требует меньше памяти для работы

из достоинств mergesort:
1) делается меньше сравнений
2) ну и озвученная тобой гарантированность n*log(n).

Вот неплохой обзорчик и сравнение.
Yandex
Объявления
06.03.2014, 20:25     QUICKsort и MERGEsort недостатки и преимущества
Ответ Создать тему
Опции темы

Текущее время: 01:34. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru