Вопросы с тегом «sorting»

алгоритмическая задача упорядочения множества элементов относительно некоторого отношения упорядочения.

308
Почему быстрая сортировка лучше, чем другие алгоритмы сортировки на практике?

В стандартном курсе алгоритмов нас учат, что быстрая сортировка в среднем составляет а в худшем случае . В то же время изучаются другие алгоритмы сортировки: в худшем случае (например, mergesort и heapsort ) и даже линейное время в лучшем случае (например, сортировка пузырьков ), но с некоторыми...

55
Что такое самый быстрый алгоритм сортировки для массива целых чисел?

Я сталкивался со многими алгоритмами сортировки во время учебы в старшей школе. Тем не менее, я никогда не знаю, какой самый быстрый (для случайного массива целых чисел). Итак, мои вопросы: Какой самый быстрый в настоящее время известный алгоритм сортировки? Теоретически, возможно, что есть еще...

35
В худшем случае

У меня проблемы с поиском хороших ресурсов, которые дают наихудший случай на месте стабильногоO ( n lnн )O(nln⁡n)O(n \ln n) алгоритма сортировки. Кто-нибудь знает какие-нибудь хорошие ресурсы? Просто напоминание, означает, что он использует переданный массив, а алгоритму сортировки разрешено...

34
Как измерить «сортировку»

Мне интересно, есть ли стандартный способ измерения "сортировки" массива? Будет ли массив с медианным числом возможных инверсий считаться максимально несортированным? Под этим я подразумеваю, что это в основном как можно дальше от сортировки или обратной...

31
Добавление элементов в отсортированный массив

Каков был бы самый быстрый способ сделать это (с алгоритмической точки зрения, а также с практической точки зрения)? Я думал что-то вроде следующего. Я мог бы добавить в конец массива и затем использовать пузырьковую сортировку, так как она имеет наилучший случай (полностью отсортированный массив в...

28
Генерация комбинаций из набора пар без повторения элементов

У меня есть набор пар. Каждая пара имеет форму (x, y), так что x, y принадлежат целым числам из диапазона [0,n). Итак, если n равно 4, то у меня есть следующие пары: (0,1) (0,2) (0,3) (1,2) (1,3) (2,3) У меня уже есть пары. Теперь я должен построить комбинацию, используя n/2пары, чтобы ни одно из...

28
Почему выборка сортируется быстрее, чем пузырьковая?

В Википедии написано, что "... сортировка выбора почти всегда превосходит сортировку по пузырькам и сортировку по гномам". Кто-нибудь, пожалуйста, объясните мне, почему сортировка выбора считается быстрее, чем сортировка пузырьком, даже если они оба имеют: В худшем случае сложность времени : O (...

25
Алгоритм распределения предметов «равномерно»

Я ищу алгоритм для распределения значений из списка, чтобы результирующий список был как можно более «сбалансированным» или «равномерно распределенным» (в кавычках, потому что я не уверен, что это лучший способ описать его ... позже я предоставлю способ измерить, если результат лучше, чем другие)....

24
Сортировка как линейная программа

У удивительного числа проблем есть довольно естественное сокращение к линейному программированию (LP). См. Главу 7 в [1] для примеров, таких как сетевые потоки, двустороннее сопоставление, игры с нулевой суммой, кратчайшие пути, форма линейной регрессии и даже оценка схемы! Поскольку оценка схемы...

23
Почему Radix Sort ?

В радикальной сортировке мы сначала сортируем по наименьшей значащей цифре, затем сортируем по второй наименьшей значащей цифре и так далее и получаем отсортированный список. Теперь, если у нас есть список из чисел, нам нужно бит, чтобы различать эти числа. Таким образом, количество проходов...

22
Нет ли алгоритма сортировки со всеми конкретными желаемыми свойствами?

На сайте Алгоритмы сортировки делается следующее заявление: Идеальный алгоритм сортировки будет иметь следующие свойства: Стабильный: равные ключи не переупорядочены. Работает на месте, требуя дополнительного пространства.O(1)O(1)O(1) Сравнение ключей в худшем случае...

22
Наименьшее количество сравнений, необходимых для сортировки (заказа) 5 элементов

Найдите наименьшее количество сравнений, необходимое для сортировки (упорядочения) пяти элементов, и разработайте алгоритм, который сортирует эти элементы, используя это количество сравнений. Решение : их 5! = 120 возможных результатов. Поэтому двоичное дерево для процедуры сортировки будет иметь...

22
Алгоритмы сортировки, которые принимают случайный компаратор

Обычные алгоритмы сортировки обычно используют набор данных для сортировки и функцию сравнения, которая может сравнивать два отдельных элемента. Если компаратор представляет собой отношение порядка¹, то результатом алгоритма является отсортированный список / массив. Мне интересно, однако, какие...

20
Практическое применение Radix Sort

Radix sort теоретически очень быстр, когда вы знаете, что ключи находятся в определенном ограниченном диапазоне, скажем, например, значений в диапазоне . Если вы просто конвертируете значения в базу что занимает время , выполните сортировку по основанию и затем преобразуйте обратно в исходную базу...

19
Какой алгоритм сортировки в постоянном пространстве наиболее эффективен?

Я ищу алгоритм сортировки для массивов int, который не выделяет ни одного байта, кроме размера массива, и ограничен двумя инструкциями: SWAP: поменять следующий индекс на текущий; MOVE: перемещает курсор к индексу +1 или -1; То есть вы не можете поменять местами не соседние индексы и не поменять...

19
Детерминированный алгоритм линейного времени, чтобы проверить, является ли один массив отсортированной версией другого

Рассмотрим следующую проблему: Вход: два массива AAA и BBB длиной nnn , где BBB в отсортированном порядке. Запрос: делать и B содержат одни и те же элементы (с учетом кратности)?AAABBB Какой самый быстрый детерминированный алгоритм для этой проблемы? Можно ли решить это быстрее, чем отсортировать...

19
Сортировать массив из 5 целых чисел с максимумом 7 сравнений

Как отсортировать список из 5 целых чисел, чтобы в худшем случае потребовалось 7 сравнений? Мне все равно, сколько других операций выполняется. Я не знаю ничего конкретного о целых числах. Я пробовал несколько разных подходов «разделяй и властвуй», которые сводят меня к 8 сравнениям, например,...

18
В чем преимущество рандомизированной быстрой сортировки?

В своей книге Рандомизированных алгоритмы , Motwani и Raghavan открыть введение с описанием их функции RandQS - Рандомизированная - где быстрой сортировкой стержень, используемый для разделения множества на две части, выбирается случайным образом . В течение некоторого времени я ломал свои мозги...

18
Почему рандомизированная быстрая сортировка имеет O (n log n) наихудших затрат времени выполнения

Рандомизированная быстрая сортировка - это расширение быстрой сортировки, в котором элемент поворота выбирается случайным образом. Что может быть наихудшим случаем временной сложности этого алгоритма. По моему мнению, это должно быть , так как наихудший случай случается, когда случайно выбранный...