Implementation (Part 2)
Урок 6 из 9 курса Быстрая сортировка — серия DSA на Coddy.
Теперь мы объединяем опорный элемент, разбиение и рекурсию в полный алгоритм.
Задание
ЛегкоТеперь объедините все это в полный алгоритм.
Напишите функцию с именем quickSort, которая принимает массив целых чисел и возвращает его отсортированным в возрастающем порядке.
Используйте последний элемент в качестве опорного (pivot), разделите остальные элементы на группу меньших и группу больших, рекурсивно вызовите quickSort для каждой группы и объедините их как отсортированные-меньшие + опорный + отсортированные-большие. Массив из 0 или 1 элемента уже отсортирован, поэтому верните его как есть.
Вы можете повторно использовать идею разбиения (partition) из предыдущего урока.
Попробуйте сами
#include <stdlib.h>
int* quickSort(int* arr, int arr_size, int* returnSize) {
// Напишите код здесь
*returnSize = arr_size;
return arr;
}
Проверьте себяВ этом уроке есть небольшой тест. Начните урок, чтобы ответить на вопросы и сохранить прогресс.
Все уроки раздела Быстрая сортировка — серия DSA
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity