QuickSort (быстрая сортировка)

Иногда на собеседовании просят написать реализацию быстрой сортировки. Суть данного алгоритма в рекурсивной сортировке массива данных с использованием разделения на 2 партиции. Необходимо отталкиваться от случайно выбранного pivot.

Визуализация алгоритма:

Напишем свою реализацию данного алгоритма на Golang.

1. Расположи файл quicksort.go в папке module3/algo

1. Напишем для начала тест.

Функция генерации данных:

Сам тест будет выглядеть так:

1. Запустим наш тест:

Все тесты проходят успешно! В следующей главе мы напишем бенчмарк и сравним производительность в сравнении с BubbleSort.