Dyzzet|
C++ Data Science
Алгоритмы
Темы · Блог · YouTube
16 января
Асимптотики

16 апреля 2021
Быстрая сортировка. Второй вариант. Интерактивная анимация

Первый вариант быстрой сортировки

Реализация быстрой сортировки со следующими аргументами функции: указатель на начало массива и его размер. В предыдущей реализации нумерация элементов подмассива всегда велась относительно начала исходного массива, в рекурсивные вызовы передавались аргументы left и right, обозначающие границы подмассивов.

Как и ранее, подмассив, с которым работает конкретный рекурсивный вызов, выделен чёрным цветом и подчёркнут синей линией. Для большей наглядности показано data[0] (значение самого левого элемента текущего подмассива).

Читать далее →
9 апреля 2021
Быстрая сортировка. Интерактивная анимация
Авторы: Dyzzet, immsmoa

Быстрая сортировка (quicksort) иначе называется сортировкой Хоара. Её идея предельно проста: в массиве выбирают некий опорный элемент (pivot), разбивают массив на две части: слева элементы меньше опорного, справа — больше. Затем процесс рекурсивно повторяется для левой и правой частей массива.

Существуют разные модификации быстрой сортировки и способы её реализации. В данном варианте в функцию передаётся массив и индексы крайних элементов: quickSort(data, 0, n- 1);. В другом варианте можно было бы передавать адрес начала массива и его размер: quickSort(data, n);.

Обратим внимание на два фрагмента из кода, который расположен далее. В каждом рекурсивном вызове водятся l = left; и r = right;, они хранят индексы крайнего левого и крайнего правого элементов.

Читать далее →
2
1
© MMXI—MMXXII. RSS. Поддержать сайт
Светлая тема / тёмная тема