Всем привет! Ранее мы разобрали пузырьковую сортировку и поговорили о том, почему она не эффективна. Ознакомиться со статьей про сортировку пузырьком и посмотреть ее код можно здесь.
В этой статье я хочу рассказать вам про один из самых эффективных алгоритмов сортировки - алгоритм быстрой сортировки.
Меня зовут Антон. Я занимаюсь front-end разработкой и сейчас я расскажу вам про алгоритм быстрой сортировки.
Разделяй и властвуй
Многие задачи в программировании можно решить с помощью алгоритма "Разделяй и властвуй". Решение задачи с помощью этого алгоритма можно свести к следующему:
- Разделяй. Разделяем задачу на подзадачи с помощью рекурсии.
- Властвуй. Как только задачи станут достаточно малы — рекурсивно решаем.
- Объединяй. Объединяем все подзадачи в одно целое, чтобы получить решение исходной задачи.
Суть метода «разделяй и властвуй» заключается в том, что мы делим задачу на меньшие подзадачи. После этого подзадачи рекурсивно вычисляются. Результаты вычисления каждой подзадачи при использовании этого метода не сохраняются.
Быстрая сортировка
Теперь, когда мы познакомились с алгоритмом "разделяй и властвуй", мы поможем приступить к разбору быстрой сортировки.
Алгоритм быстрой сортировки в основном работает путем разбиения всего массива, а затем рекурсивного разбиения левой и правой частей массива до тех пор, пока весь массив не будет отсортирован. Левая и правая части массива определяют индекс и возвращают его значение после каждой операции.
Существует множество способов найти значение разделителя (элемента, который будет делить массив на две части) . Некоторые алгоритмы берут первый элемент в качестве опорного. Это не самый лучший выбор, потому что он дает наихудшие показатели для уже отсортированных массивов. Лучше взять в качестве разделителя элемент из середины.
В методе быстрой сортировки выбирается значение из основного списка, которое называется опорным значением. Остальные значения разделяются на два списка:
- Первый список содержит значения, которые меньше либо равны опорному значению. Эти значения располагаются слева от опорного значения.
- Второй список содержит значения, которые больше опорного значения. Эти значения располагаются справа от опорного значения.
Метод быстрой сортировки повторяется для всех результирующих списков, пока не останется только одно значение или пустой список значений.
После этого вы выбираете последнее одиночное значение, и если значение располагается слева от опорного значения, оно остается таким, пока вы не дойдете до первого опорного значения вверху.
Код реализации этого алгоритма на JavaScript
Сложность данного алгоритма равна:
O(n log n)
Именно поэтому его называют алгоритмом быстрой сортировки. Он работает быстрее других алгоритмов и гораздо быстрее сортировки пузырьком
#it #frontend #code #top #proweb #web #программирование #работа