Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.55/11: Рейтинг темы: голосов - 11, средняя оценка - 4.55
2 / 2 / 2
Регистрация: 20.02.2014
Сообщений: 34
1

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

06.03.2014, 19:37. Просмотров 2119. Ответов 1
Метки нет (Все метки)

Добрый вечер!
Qsort плоха тем, что в худшем случае работает за О(n^2). Mergesort стабильна и работает ВСЕГДА за n*log(n).
Расскажите, пожалуйста, поподробнее, в чем преимущество quicksort? Чем она лучше mergesort?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
06.03.2014, 19:37
Ответы с готовыми решениями:

Какие преимущества и недостатки потоковых операций ввода-вывода
Здравствуйте! Какие вы знаете преимущества и недостатки потоковых операций ввода-вывода?

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

Не работает сортировка (MergeSort)
#include <stdio.h> #include <stdlib.h> #include <conio.h> #include <string.h> const int N =...

Реализация многопоточной mergesort на windows
Необходимо было реализовать многопоточную сортировку слияниями массива целых чисел по возрастанию,...

1
13388 / 7064 / 1698
Регистрация: 30.01.2014
Сообщений: 11,782
06.03.2014, 20:25 2
у quicksort есть практические достоинства:
1) хорошо распараллеливается
2) обладает более высокой локальностью, на каком-то уровне рекурсии кусок может быть полностью закеширован, а это значительно ускорит процесс
3) требует меньше памяти для работы

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

Вот неплохой обзорчик и сравнение.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
06.03.2014, 20:25

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

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

Сортировки Heapsort, Mergesort, Quicksort
Здравствуйте, очень срочно нужна помощь. Помогите сопоставить несколько сортировок в одном файле....

Работа за рубежом. Преимущества и недостатки.
Что вы можете сказать про работу зарубежом? Какие она имеет преимущества и недостатки перед работой...

Преимущества и недостатки Windows Forms
Какие плюсы и минусы у Windows Forms? Чем удобна? Добавлено через 6 часов 32 минуты поднимаю


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

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

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