Публикации по теме 'quicksort'
K-й наибольший элемент (с быстрой сортировкой)
Допустим, у нас была эта проблема:
Учитывая массив целых чисел nums и целое число k , вернуть самый большой kth элемент в массиве .
Обратите внимание, что это kth самый большой элемент в отсортированном порядке, а не kth отдельный элемент.
Примечание. Существует способ решить эту проблему без сортировки, но для объяснения быстрой сортировки я воспользуюсь и реализую его.
Быстрая сортировка
Для начала допустим, что у нас есть массив, состоящий из нескольких целых..
Вопросы по теме 'quicksort'
Quicksort медленнее, чем Mergesort?
Вчера я работал над реализацией быстрой сортировки, а затем запустил ее, ожидая более быстрого выполнения, чем сортировка слиянием (которую я также реализовал). Я выполнил оба, и хотя быстрая сортировка была быстрее для небольших наборов данных - 100...
8494 просмотров
schedule
25.10.2022
QuickSort против MergeSort, что я делаю не так?
Я пытаюсь реализовать несколько алгоритмов сортировки на Java, чтобы сравнить производительность. Из того, что я прочитал, я ожидал, что quickSort будет быстрее, чем mergeSort, но в моем коде это не так, поэтому я предполагаю, что с моим алгоритмом...
1196 просмотров
schedule
23.07.2022
Способен ли QuickSort переполнять стек?
В моем коде метод будет вызывать сам себя (рекурсия). Мы знаем, что глубокий вызов метода приведет к переполнению стека. Итак, произойдет ли переполнение стека при большом количестве данных?
Мой код QuickSort: (внутренний класс класса сортировки)...
191 просмотров
schedule
31.03.2024
быстрая сортировка производительности на месте (python)
Меня попросили написать версию Quicksort «на месте». Созданы две внутренние функции - рекурсивная и "сортировка на месте", которая выбирает случайный свод (требуется вопрос), сортирует список на месте и возвращает индекс свода после сортировки....
297 просмотров
schedule
16.05.2024
Повторяемость для наихудшего времени выполнения быстрой сортировки
Предположим, мы построили быструю сортировку, и значение разворота занимает линейное время. Найдите повторение для наихудшего времени выполнения.
Мой ответ: T(n)= T(n-1) + T(1) + тета(n)
Худший случай возникает, когда подмассивы полностью...
27153 просмотров
schedule
14.02.2024
Быстрая сортировка с двойным связанным списком
У меня возникли проблемы с методом обмена в программе быстрой сортировки. Я реализую его из метода QuickSort, который сортирует массивы. Здесь я беру файл с целым числом в каждой строке, он помещает число в двусвязный список, затем сортирует список...
465 просмотров
schedule
19.05.2024
Рекурсивная быстрая сортировка возвращает только результат первого рекурсивного вызова
Я пытаюсь реализовать быструю сортировку в Python на основе псевдокода, который я прочитал в классе, но он не сортирует список. Он выполняет рекурсию и всегда возвращает результат первого рекурсивного вызова (который не отсортирован). Может ли...
32 просмотров
schedule
01.11.2023
Ошибка переполнения стека с быстрой сортировкой и медианной реализацией
Прежде всего, я просто хочу заявить, что это вопрос домашнего задания, над которым я предпринял множество попыток.
Меня попросили изменить быструю сортировку в Java, чтобы установить опорную точку как псевдомедиану 9 значений в массиве, используя...
217 просмотров
schedule
07.02.2024
Каков максимальный размер стека вызовов функций при быстрой сортировке массива из N элементов только с двумя разными ключами
На самом деле, это вопрос из Алгоритма Седжвика в Принстоне от Coursera. Я думаю, что это ~ log2 (N). Но я запускаю эксперимент, когда 0,5N 1s 0,5N 0s меняются местами, это ~ 2ln (N), когда N различных ключей, это ~ 2log2 (N), так почему?
Вот код...
142 просмотров
schedule
03.11.2023
Быстрая сортировка. В худшем случае это приводит к переполнению стека?
Я пытаюсь реализовать алгоритм быстрой сортировки, в котором я выбираю опорную точку как самый правый элемент. Однако, когда массив из ~ 4000 элементов уже отсортирован, происходит переполнение стека. Это моя реализация:
void...
269 просмотров
schedule
10.01.2024
Быстрая сортировка, разбивающая бесконечный цикл
arr = [7, 3, 5, 6, 7, 1, 8, 0, 4, 9, 6, 2]
def partitioning(arr, l, d):
pivot = 5
while l <= d:
while arr[l] < pivot:
l += 1
while arr[d] > pivot:
d -= 1
arr[l], arr[d] = arr[d],...
188 просмотров
schedule
20.10.2022
Метод подкачки для быстрой сортировки в java
Может ли кто-нибудь помочь мне понять этот метод подкачки, который является частью более крупной программы быстрой сортировки? Предполагается взять массив и два целых числа и поменять местами позиции индекса, указанные целыми числами.
private...
2110 просмотров
schedule
21.01.2024
Сортировка Gnome быстрее, чем быстрая сортировка?
Я решил углубиться в алгоритмы сортировки и реализовал некоторые из них, такие как пузырь, выделение, гном, вставка, слияние и быстрая сортировка на питоне. Однако, когда я запустил их и сравнил время, сортировка gnome, которая составляет O (n ^ 2),...
417 просмотров
schedule
28.03.2024
Почему моя реализация Quicksort вызывает переполнение стека?
у меня есть этот код
public static void quicksort(int[] array){
quicksort(array, 0, array.length - 1);
}
public static void quicksort(int[] array, int min_index, int max_index){
if(array.length <= 1 || min_index >=...
42 просмотров
schedule
11.04.2024
java - код для подсчета сравнений и времени выполнения для алгоритмов, которые не выводятся правильно
В моем задании Java я должен подсчитать количество сравнений, а также общее время выполнения алгоритмов сортировки выбором, сортировкой вставкой, пузырьковой сортировкой, быстрой сортировкой и сортировкой слиянием. Следующий код представляет собой...
1350 просмотров
schedule
05.03.2024
C: сортировка двумерных массивов построчно с использованием qsort
Итак, чего я пытаюсь добиться здесь, так это использовать реализацию C qsort в массиве 2d, ведь я хочу, чтобы только строки сортировались на основе его первого элемента, например:
int arr[3][2]={{65,1},
{45,2},...
557 просмотров
schedule
10.10.2022
Алгоритм быстрой сортировки не работает из-за ошибки StackOverflow
Я работаю над модифицированной версией Quicksort, которая использует формулу ((lowIndex + highIndex) / 2) для определения раздела.
Мой код ниже. Однако всякий раз, когда я запускаю его, я получаю следующую ошибку:
start ARRAY
1
2
10
9
3
4
8...
73 просмотров
schedule
03.09.2022
Рандомизированная глубина рекурсии быстрой сортировки
Я читаю Освещенные алгоритмы: часть 1 , и задача 5.3 гласит:
Пусть ⍺ — некоторая константа, не зависящая от длины входного массива n и находящаяся строго между 0 и 1/2. Предположим, что вы достигли приблизительно сбалансированного разделения...
206 просмотров
schedule
14.10.2022
Быстрая сортировка не может последовательно сортировать наборы данных из 100 000 целых чисел
Я реализовал несколько вариантов алгоритма быстрой сортировки на C++, но все они имеют один большой недостаток. Им не удается отсортировать наборы данных из 100 000 целых чисел за разумное время. Иногда наборы данных из 10 000 целых чисел также...
88 просмотров
schedule
16.11.2022
Рандомизированная быстрая сортировка, при которой после разделения снова выбирается точка опоры.
Я хотел бы придумать повторение для этой проблемы:
Рассмотрим вариант рандомизированного алгоритма быстрой сортировки, в котором опорная точка выбирается случайным образом до тех пор, пока массив не будет разделен таким образом, что и нижний...
180 просмотров
schedule
22.10.2022
