Публикации по теме 'quicksort'
Быстрая сортировка объяснила непомерно умному пятилетнему ребенку
Разочарованный обилием непрозрачных и запутанных объяснений, я решил написать свое собственное.
Предполагается, что этот пятилетний ребенок имеет базовое представление о массивах и о том, почему компьютеры не могут просто сортировать их интуитивно, как мы.
Быстрая сортировка — это алгоритм сортировки по принципу "разделяй и властвуй" .
Что такое алгоритм сортировки по принципу "разделяй и властвуй"?
Это означает, что это процесс, который решает проблему сортировки массива..
Вопросы по теме 'quicksort'
Худший случай для QuickSort — когда это может произойти?
При анализе QS все всегда ссылаются на «почти отсортированный» наихудший случай. Когда такой сценарий может произойти с естественным входом?
Единственный пример, который я придумал, — это переиндексация.
74807 просмотров
schedule
14.01.2024
Требования к итератору быстрой сортировки
Вкратце: Можно ли эффективно реализовать быструю сортировку двусвязного списка? До того, как я подумал об этом, я понял, что нет.
На днях у меня была возможность рассмотреть требования к итератору для базовых алгоритмов сортировки. Основные...
1478 просмотров
schedule
05.10.2022
можно ли сделать быструю сортировку списка только с одним проходом?
Я изучаю haskell, и я вижу определение функции:
quickSort (x : xs) = (quickSort less) ++ (x : equal) ++ (quickSort more)
where less = filter (< x) xs
equal = filter (== x) xs
more =...
795 просмотров
schedule
10.06.2024
Алгоритм быстрой сортировки неправильно назначает точку опоры
Я видел эту фантастическую визуализацию алгоритма быстрой сортировки: http://www.youtube.com/watch?v=Z5nSXTnD1I4
Я почувствовал, что действительно понял принципы быстрой сортировки, и с помощью нескольких руководств в Интернете приступил к...
1410 просмотров
schedule
30.10.2022
Откатывается ли реализация быстрой сортировки в Linux к сортировке вставками?
Я читал в Bentley & McIlroy (1993), что предложенная ими реализация быстрой сортировки использует сортировку вставками, когда массивы становятся достаточно маленькими.
Мне было любопытно узнать, используют ли современные ядра тот же маневр....
991 просмотров
schedule
28.10.2022
Выбор стержня для алгоритма дублирования ключей
Я пытаюсь понять, как выбрать точку опоры при поиске повторяющихся ключей в массиве. Большинство примеров, которые я видел, всегда выбирали первый элемент в качестве точки поворота, делая вид, что этот элемент дублируется в массиве. Что, если это не...
86 просмотров
schedule
13.03.2024
Является ли эта быстрая сортировка стабильной?
Я вот что сложно сделать стабильной быстрой сортировкой. Однако моя быстрая сортировка кажется стабильной.
quicksortBy _ []=[]
quicksortBy key (pivot:rest)=
(quicksortBy key [little|little<-rest, key little < key pivot])
++ [pivot]...
451 просмотров
schedule
08.11.2022
В чем разница между быстрой сортировкой с двойным поворотом и быстрой сортировкой?
Я никогда раньше не видел быстрой сортировки с двойным поворотом. Это обновленная версия быстрой сортировки? И в чем разница между быстрой сортировкой с двойным поворотом и быстрой сортировкой?
33587 просмотров
schedule
22.11.2023
Алгоритмы быстрой сортировки. Много разных способов сделать одно и то же?
Правильно ли я говорю, что существует много способов выполнить быструю сортировку?
Для аргументации давайте использовать номера первого учебника: 20 47 12 53 32 84 85 96 45 18
В этой книге сказано поменять местами 18 и 20 (в книге 20...
664 просмотров
schedule
26.12.2023
Переполнение стека QuickSort для отсортированных массивов (работает для других наборов данных)
Поэтому я изо всех сил старался оптимизировать свой алгоритм быстрой сортировки, чтобы он работал как можно эффективнее даже для отсортированных или почти отсортированных массивов, используя сводную точку, которая является медианой трех значений, а...
274 просмотров
schedule
21.11.2023
сортировка по ленивой последовательности хэш-карт в clojure
Мне нужно взять 20 результатов из ленивой последовательности миллионов хэш-карт, но чтобы эти 20 были основаны на сортировке по различным значениям в хэш-картах.
Например:
(def population [{:id 85187153851 :name "anna" :created #inst...
474 просмотров
schedule
16.11.2022
Можете ли вы выбрать любую точку поворота в быстрой сортировке?
Недавно я увидел Quick Sort - Computerphile видео на Youtube о том, как работает быстрая сортировка (на бумаге) , и у меня есть вопрос. Представьте, что у нас есть массив, содержащий, например, "27,6,19,2,15,9,10" . Сначала я выбираю 10 в...
499 просмотров
schedule
31.01.2024
Превышение лимита времени в Spoj
Я пытаюсь решить эту проблему http://www.spoj.com/problems/TSORT/ но я получаю эту ошибку, лимит времени превышен. Мой код правильно компилируется и сортируется на моем компьютере, но когда я отправляю его в spoj, он возвращает эту ошибку....
430 просмотров
schedule
18.01.2024
Переполнение стека, когда массивы становятся слишком большими
Я пытаюсь реализовать версию быстрой сортировки с тестовыми классами, которая принимает float. Когда я пытаюсь сгенерировать массивы размером 10⁸, я получаю переполнение стека при запуске моего тестового класса.
Я пробовал с размером массива 10⁷,...
137 просмотров
schedule
20.05.2024
Что на самом деле означает для некоторой константы c в алгоритмическом анализе? (например, быстрая сортировка)
Рассмотрим следующее дерево рекурсии для быстрой сортировки, которая постоянно делит подзадачи в соотношении 3 к 1 (источник: Khan Academy ).
Я понимаю, что подпрограмма разделения в быстрой сортировке перебирает каждую подзадачу и, таким...
261 просмотров
schedule
13.12.2023
Какова пространственная сложность хвостовой рекурсивной быстрой сортировки?
Глядя на следующий псевдокод хвостовой рекурсии быстрой сортировки
QuickSort(A[1, ..., n], lo, hi)
Input: An array A of n distinct integers, the lower index and the higher index
// For the first call lo = 1 and hi = n
Output: The array A...
504 просмотров
schedule
28.11.2022
Ошибка Stackoverflow в моем алгоритме быстрой сортировки
Я работал над этим кодом несколько дней безуспешно из-за ошибки переполнения стека во время рекурсии.
Проблема заключается в том, что наша точка опоры всегда является 0-м элементом, и с помощью рекурсии мы можем сортировать массив, либо меняя...
71 просмотров
schedule
26.01.2024
Быстрая сортировка в js
Я нашел эту статью на среде, и я пытаюсь понял, что на самом деле делает код.
это код:
помощник
const defaultComparator = (a, b) => {
if (a < b) {
return -1;
}
if (a > b) {
return 1;
}
return 0;
};
функция...
79 просмотров
schedule
15.01.2024
Как я могу создать массивы для тестирования Best Case of quickSort?
Я хочу проверить временную сложность quickSort, но я не знаю, как генерировать массивы для тестирования в лучшем случае. В моей версии quickSort в качестве точки поворота используется последний элемент массива.
191 просмотров
schedule
05.12.2022
изменение места оценки поворота приводит к сбою QuickSort
В QuickSort оценка сводной точки перед условиями сортировки заставляет алгоритм работать, а использование его индекса для получения значения в рамках условий приводит к его сбою, хотя опорный индекс вычисляется заранее и не должен меняться, в отличие...
29 просмотров
schedule
14.06.2024
