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

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

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

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

06.03.2014, 19:37. Просмотров 649. Ответов 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++
Доброго времени суток! 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++11 - C++
Написал быструю сортировку, добился работоспособности и сразу захотелось улучшить сам код. #include <iostream> #include...

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

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

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

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

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

QuickSort найдите ошибку - C++
Не правильно сортирует массив, подскажите в чем ошибка.... #include <iostream> using namespace std; int partition(int A,int p,int r);...


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

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

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

Вот неплохой обзорчик и сравнение.
Ответ Создать тему
Опции темы

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