Алгоритмы и структуры данных

Быстрая сортировка

Это алгоритм сортировки, который эффективно сортирует элементы, разделяя входные данные на более мелкие подзадачи. Он работает путем выбора элемента «pivot» из входных данных и разделения других элементов на два подмассива: элементы меньше, чем «pivot», и элементы, превышающие «pivot». Он рекурсивно сортирует два подмассива.

Алгоритм:
1. Выбор «pivot» из входного массива. (Его выбор может существенно повлиять на производительность алгоритма. Это может быть: первый, последний или случайный элемент).
2. Разделение элементов массива так, чтобы все элементы меньше «pivot» находились перед ним, а все элементы выше «pivot» — после нее.
3. Рекурсивное примените алгоритма быстрой сортировки к подмассиву элементов, меньших опорного, и к подмассиву элементов, превышающих опорный.
4. Продолжайте этот процесс, пока весь массив не будет отсортирован.

Сложность алгоритма:
В лучшем случаи: O(n logn)
В cреднем: O(n logn)
В худшем: O(n^2)

www.tgoop.com/the_algorithms/4550

13.1K viewsedited  Sep 21, 2023 at 15:00

Быстрая сортировка

Это алгоритм сортировки, который эффективно сортирует элементы, разделяя входные данные на более мелкие подзадачи. Он работает путем выбора элемента «pivot» из входных данных и разделения других элементов на два подмассива: элементы меньше, чем «pivot», и элементы, превышающие «pivot». Он рекурсивно сортирует два подмассива.

Алгоритм:
1. Выбор «pivot» из входного массива. (Его выбор может существенно повлиять на производительность алгоритма. Это может быть: первый, последний или случайный элемент).
2. Разделение элементов массива так, чтобы все элементы меньше «pivot» находились перед ним, а все элементы выше «pivot» — после нее.
3. Рекурсивное примените алгоритма быстрой сортировки к подмассиву элементов, меньших опорного, и к подмассиву элементов, превышающих опорный.
4. Продолжайте этот процесс, пока весь массив не будет отсортирован.

Сложность алгоритма:
В лучшем случаи: O(n logn)
В cреднем: O(n logn)
В худшем: O(n^2)

BY Алгоритмы и структуры данных