Описание тега counting-sort
Подсчетная сортировка - это метод сортировки, основанный на ключах между определенным диапазоном. Он работает, подсчитывая количество объектов, имеющих разные ключевые значения (вид хеширования). Затем выполните некоторые арифметические действия, чтобы вычислить положение каждого объекта в выходной последовательности.
1
ответ
Заменить 2d массив пузырьковой сортировки на счетную сортировку
Следующий код сортирует строки по первому элементу, используя метод bubble. Я не могу изменить это на счет сортировки. public void SortStack(double[,] n) { for (int i = 0; i < n.GetLength(0) - 1; i++) { for (int j = i; j < n.GetLength(0); j++)…
18 ноя '15 в 22:04
1
ответ
Пытаясь понять сложность подсчета сортировки
Читая о разных видах. В случае сортировки с подсчетом, код C ниже работает нормально, но у меня есть вопрос о его сложности времени. На самом деле это не O(N), как я читаю во многих местах, а O (максимальное значение входного массива - минимальное з…
13 мар '12 в 16:17
2
ответа
Отсортируйте массив из n элементов, чтобы первые k-элементы были самыми низкими в порядке возрастания (алгоритм на месте)
Это домашний вопрос, на котором я застрял. Мне нужно отсортировать массив из n элементов, чтобы первые k-элементы были самыми низкими и находились в порядке возрастания. Для k <= n/log(n) алгоритм должен быть O(n). Мои решения: простое решение, о ко…
15 июн '14 в 03:35
2
ответа
Почему временная и пространственная сложность подсчета сортировки равна O(n + k), а не O(max(n, k))?
Здесь 'n' и 'k' - это размер входного массива и максимальный элемент массива соответственно. Так как в массиве размера 'n' есть один прогон для подсчета частоты элементов и отдельного прогона в массиве размера 'k' и для каждого прохода (или итерации…
11 окт '18 в 18:15
1
ответ
Сортировка огромного массива целых чисел, каждое из которых представлено 10 битами
Для такой проблемы - как отсортировать массив целых чисел, где каждое целое число представлено 10-битным? Я считаю, что мы можем использовать счет сортировки. Но если я немного подправлю проблему, чтобы каждый элемент представлял собой комбинацию це…
05 мар '14 в 00:03
2
ответа
Проблема с реализацией алгоритма сортировки
Я пытаюсь научить себя нескольким алгоритмам сортировки в python, и у меня возникли небольшие проблемы с выводом. Я пытаюсь реализовать алгоритм сортировки подсчета, и я получил это далеко: def counting_sort(l): nums = l highest = max(nums) + 1 help…
28 янв '17 в 00:47
1
ответ
Сортировка по имени
У меня проблемы с сортировкой имен в алфавитном порядке с использованием сортировки по счетам, например, я полагаю, что сортировать в алфавитном порядке и добавить к нему, например, ввод числа 0001 Alex Smith, Gregory John, Alex Smith, Adam Richard,…
27 сен '11 в 06:19
3
ответа
Почему подсчет сортировки не используется для больших входов?
Счетная сортировка - это алгоритм сортировки со средней сложностью по времени O(n+K), а сортировочная сортировка предполагает, что каждый входной элемент является целым числом в диапазоне от 0 до K. Почему мы не можем выполнить линейный поиск максим…
27 дек '14 в 15:43
1
ответ
Странные результаты при измерении сортировки по Radix
Я измеряю время выполнения сортировки Radix и Counting, используя timeit модуль. Я использую 100 наборов случайных целых чисел, лежащих на интервале <0; 1000000>. Все целые числа уникальны в наборе. Первый набор состоит из 10000 целых чисел, последн…
28 дек '14 в 14:45
2
ответа
Подсчет сортировки в односвязном списке C#
Есть ли способ сделать счетную сортировку в односвязном списке? Я не видел ни одного примера, и довольно сложно сделать это без них. У меня есть пример этого в массиве, и я хотел бы сделать это в односвязном списке. Кто-нибудь делал это в односвязно…
02 мар '17 в 19:13
1
ответ
Найти максимальное число повторений в O(n) времени и O(1) лишних пробелах
Найдите максимальное число повторений (число, которое встречается чаще всего) за время O(n) и дополнительное пространство O(1). Я думаю, что я могу использовать фазу подсчета сортировки, которая поддерживает массив счетчиков, тогда это можно сделать…
31 авг '16 в 13:58
0
ответов
Как отсортировать текстовый файл, чтобы найти анаграммы за O(MN) сложности времени, где M - максимальное количество символов, а N - количество слов?
Привет, я новичок в Python и хочу найти группы анаграмм в файле за линейное время. Анаграммы - это, в основном, два или более слов, которые состоят из одного и того же алфавита, но в разных расположениях. Сначала я прочитал все слова в список. По-ви…
03 авг '18 в 07:52
0
ответов
Подсчет сортировки присутствует в std: sort в STL?
Счетная сортировка имеет временную сложность: O(n+k) n-> размер ввода k-> abs. разн. ч / б мин и макс. В некоторых случаях подсчет сортировки лучше, чем алгоритм сортировки на основе сравнения. Он присутствует в std: sort в STL? если нет, есть ли пр…
06 май '18 в 11:44
1
ответ
Не получается правильно отсортированный массив с сортировкой
В настоящее время я работаю над алгоритмом подсчета сортировки. Я установил два временных массива C а также B, C заключается в подсчете количества появлений числа в исходном массиве. Затем он использует элементы в C разместить элементы в A (исходный…
18 окт '17 в 16:15
1
ответ
Что плохого в следующей программе сортировки?
Вот моя программа сортировки для подсчета: public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int arr[] = new int[n]; int b[] = new int[n+1]; for (int i = 0; i < n; i++) { arr[i] = sc.nextInt(); } …
23 окт '13 в 20:04
1
ответ
Уменьшение количества элементов в алгоритме сортировки
Я реализовал алгоритм сортировки отсчетов из псевдокода. В псевдокоде последний цикл уменьшается C[A[j]] после первого прохода. Это смещало все вправо, поэтому я отлаживал и декрементировал перед первым проходом, чтобы получить правильные результаты…
21 сен '13 в 19:56
2
ответа
Подсчет ошибки сортировки сортировки в C
Ниже моя попытка подсчета. Я изобразил свою логику, пробежался по ней в устной форме и тщательно прокомментировал свой код. Однако мой код вызывает ошибку сегментации. Я понимаю, что ошибка сегментации представляет недопустимый доступ к памяти, поэт…
04 май '17 в 03:16
1
ответ
Стоит ли использовать сортировку по счету или любую другую альтернативу для сортировки частот по сложности символов?
У меня будет массив символов (256 символов ascii) и массив их частот (некоторые символы встречаются ноль раз). Было бы предпочтительнее использовать сложную систему подсчета для сортировки, и что будет занимать больше строк кода (код будет написано …
06 апр '17 в 10:12
2
ответа
Используя основную сортировку / счетную сортировку для массива структур в C?
У меня есть массив структур, который содержит тип uint32_t. Зная максимальные и минимальные значения массива, я хочу реализовать сортировку подсчета или сортировку по основанию для сортировки массива на основе uint32_t. Диапазон значений может быть …
08 май '15 в 19:34
1
ответ
Как я могу оптимизировать время этого алгоритма CountingSort в Scala
Я хотел бы попросить вас помочь определить, какая часть моего кода неэффективна. Я сравниваю алгоритм QuickSort с алгоритмом CountingSort, предполагая, что количество элементов в Array[Byte] меньше 16 Однако время CountingSort намного выше, чем врем…
29 ноя '18 в 01:57