Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.91/11: Рейтинг темы: голосов - 11, средняя оценка - 4.91
SunFox25
5 / 4 / 2
Регистрация: 09.08.2018
Сообщений: 27
1

Сортировка Слиянием vs Быстрая Сортировка - что лучше

13.08.2018, 16:21. Просмотров 1978. Ответов 6

Народ, помогите разобраться какой из методов сортировки лучше "Сортировка Слиянием" или "Быстрая Сортировка":
у быстрой худшее время O(n ^ 2), а у сортировки слиянием O(n log n);
среднее время одинаковое - O(n log n);
лучшее - у сортировки слиянием O(n log n), а у быстрой - O(n log n) (обычное разделение) или O(n) (разделение на 3 части);
Затраты пямяти опять же лучше у сортировки слиянием - O(n) вспомогательных, против O(n) вспомогательных + O(log n) вспомогательных у быстрой

Мне почему-то кажеться, что сортировка слиянием лучше, хотя я конечно не разбираюсь в том, что такое это большое "О" и что означает "n log n" (я не понял их перемножить надо (n и логарифм из n) или как?).

Если есть специалист - пожалуйста, разъясните, какой метод всё-таки эффективнее. А то у меня стоит для сортировки текстур сортировка слиянием, а сейчас наткнулся на быструю сортировку, и не знаю, что эффективней.
0
Лучшие ответы (1)
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.08.2018, 16:21
Ответы с готовыми решениями:

3.1 Посмотрите, вроде быстрая сортировка, в любом случае, можете переделать(лучше под с++)?
#include <stdio.h> #include <conio.h> #include <clocale> #include <stdlib.h> #include <math.h>...

Сортировка слиянием. В каком куске кода происходит сортировка и каким именно образом?
Помогите, пожалуйста, разобраться. Подскажите в каком куске кода происходит сортировка и каким...

Что такое быстрая сортировка?
как работает и и для чего она применяется?:(

Быстрая сортировка. Что не так?
Всем привет. Задание - написать квиксорт с уменьшенной глубиной рекурсии, то есть "сначала...

Подскажите что не в моем коде(Сортировка слиянием)
Я не очень понимаю где именно неверно в моем коде. Хотел рассортировать массив методом слияния....

6
Human_foot
129 / 85 / 31
Регистрация: 27.06.2018
Сообщений: 222
13.08.2018, 16:44 2
Лучший ответ Сообщение было отмечено SunFox25 как решение

Решение

В гугле первые строки. Вот теория с графиками и таблицами сравнений
https://habr.com/post/188010/
https://ru.wikipedia.org/wiki/Временная_сложность_алгоритма
http://bigocheatsheet.com
1
anapshy
255 / 236 / 199
Регистрация: 14.11.2016
Сообщений: 892
Завершенные тесты: 3
13.08.2018, 16:55 3
По мне так сортировка слиянием. В прочем если входных данных не много, то как-то и без разницы.

Добавлено через 1 минуту
Цитата Сообщение от SunFox25 Посмотреть сообщение
"n log n" (я не понял их перемножить надо или как?).
Да.
0
SunFox25
5 / 4 / 2
Регистрация: 09.08.2018
Сообщений: 27
13.08.2018, 19:49  [ТС] 4
Спасибо большое. Оказалось что самая эффективная сортировка - "Поразрядная Сортировка". Но это наверное только для целых чисел, а мне надо для float. Есть ли какой-нибудь способ выполнить поразрядную сортировку для типов float/double?
0
nonedark2008
1280 / 949 / 289
Регистрация: 28.07.2012
Сообщений: 2,620
13.08.2018, 20:32 5
Цитата Сообщение от SunFox25 Посмотреть сообщение
Есть ли какой-нибудь способ выполнить поразрядную сортировку для типов float/double?
Если числа положительные, то втупую конвертируешь указатель на массив float в указатель на массив целых беззнаковых чисел того же размера. Отношение порядка при этом сохраняется. Если есть отрицательные числа, то чуть сложнее.
0
SunFox25
5 / 4 / 2
Регистрация: 09.08.2018
Сообщений: 27
14.08.2018, 03:49  [ТС] 6
Что-то я не уверен, что при таком способе получиться сортировать числа с плавающей запятой, можно пожалуйста доказательства. И как быть с отрицательными числами не могу понять, они очень нужны.
0
nonedark2008
1280 / 949 / 289
Регистрация: 28.07.2012
Сообщений: 2,620
14.08.2018, 08:15 7
Цитата Сообщение от SunFox25 Посмотреть сообщение
доказательства
Доказательство напрямую следует из стандарта IEEE-754, который практически везде используется для представления чисел с плавающей точкой. Можешь вручную расписать числа и убедиться.
Цитата Сообщение от SunFox25 Посмотреть сообщение
И как быть с отрицательными числами не могу понять
Если в массиве будут отрицательные числа, то после сортировки он будет почти упорядочен. Необходимо будет немного переставить элементы.
0
14.08.2018, 08:15
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.08.2018, 08:15

Быстрая сортировка(сортировка Хоара). Отсортировать фрагмент массива
Мне нужно отсортировать фрагмент массива, расположенный между первым и последним отрицательным...

Быстрая сортировка (сортировка Хоара) для связных списков
есть у кого готовый алгоритм? или подскажите как реализовать

2 сортировки: пирамидальная сортировка и сортировка слиянием
Реализовать два улучшенных алгоритма сортировки. Для каждого алгоритма вычислить показатель...


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

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

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