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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
ferc
2 / 2 / 1
Регистрация: 20.02.2014
Сообщений: 34
#1

QuickSort и MergeSort: недостатки и преимущества - C++

06.03.2014, 19:37. Просмотров 655. Ответов 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: недостатки и преимущества (C++):

Преимущества и недостатки при реализации стека, очереди и дека через дин. массива - C++
Доброго времени суток! 1) Назовите преимущества и недостатки реализации очереди с помощью динамического массива. 2) Назовите...

Не работает сортировка (MergeSort) - C++
#include <stdio.h> #include <stdlib.h> #include <conio.h> #include <string.h> const int N = 4000; int L,R; char...

проверте где ошибка в mergeSort - C++
main.cpp #include <iostream> #include <fstream> #include <vector> #include <iomanip> #include "merge_sort.h" #include...

QuickSort - C++
Помогите с алгоритмом и кодом на C++ быстрой сортировки! Наработок вообще нет!

Quicksort - C++
Дан массив, необходимо отсортировать его в порядке возрастания. Использую квиксорт, но в одном из тестов не проходит по времени (2с). ...

QuickSort на C++11 - C++
Написал быструю сортировку, добился работоспособности и сразу захотелось улучшить сам код. #include <iostream> #include...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
DrOffset
7090 / 4231 / 950
Регистрация: 30.01.2014
Сообщений: 7,006
06.03.2014, 20:25 #2
у quicksort есть практические достоинства:
1) хорошо распараллеливается
2) обладает более высокой локальностью, на каком-то уровне рекурсии кусок может быть полностью закеширован, а это значительно ускорит процесс
3) требует меньше памяти для работы

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

Вот неплохой обзорчик и сравнение.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.03.2014, 20:25
Привет! Вот еще темы с ответами:

stdlib.h - quicksort - C++
Идея такова: отсортировать массив A очень быстрым методом Хоара. Пробовал в stdlib.h делать QuickSort - ничего не получилось. Все значения...

Реализация QuickSort - C++
Ребят, есть нужда отсортировать массив структур по полю name (по алфавиту) реализовав алгоритм QuickSort. Написал вроде как черновой...

Сортировка методом QuickSort - C++
Я только недавно начал изучать програмирование. Нужно отсортировать масив методом QuickSort, суть метода я понял. Все способы...

Число перестановок QuickSort - C++
Здравствуйте! Подскажите пожалуйста, как можно посчитать число перестановок QuickSort. Имеется массив на 10,000 элементов


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

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru