Сегодняшний вопрос касался частичного применения алгоритма быстрой сортировки. Следовательно, я получил возможность узнать, как работает алгоритм быстрой сортировки. В какой-то момент я застрял из-за некоторых сомнений, но мне удалось преодолеть это, получить результат и опубликовать его на моем Гитхабе.
Q - Учитывая массив и число k, где k меньше размера массива, нам нужно найти kᵗʰ наименьший элемент в данном массиве. Дано, что все элементы массива различны.
Этот метод называется Быстрый выбор, так как это частичная реализация алгоритма Быстрой сортировки.
Основная идея этого быстрого метода состоит в том, чтобы найти правильный индекс опорной точки, сопоставить его с k и затем вернуть его элемент. Если он не совпадает, мы проверяем, лежит ли k справа или слева от опорной точки, а затем создаем одиночный подмассив (в отличие от алгоритма Quicksort) и, соответственно, снова выполняем ту же функцию. Это продолжается до тех пор, пока мы не найдем точку опоры в самой позиции kᵗʰ.
Output: The 9th minimum number in the array is 17
Ссылка: этот код был предоставлен ita_c на GeeksForGeeks.
Проблемы, с которыми я столкнулся при работе над этим вопросом
- Я не мог понять, почему k обновляется на каждой итерации.
- Кроме того, я не мог понять, почему l было вычтено из индекса точки поворота (pivot_in− l) в строке 19.
Оба сомнения были решены в этом вопросе о переполнении стека.
Если есть какие-либо исправления в коде или пояснении, сделайте комментарий. Спасибо, что прочитали!
