QuickSort (быстрая сортировка): бенчмарк и сравнение с BubbleSort

Напишем бенчмарк и сравним производительность в сравнении с BubbleSort.

1. Функция генерации больших данных выглядит следующим образом:

Функция выше генерирует многомерный массив (слайс слайсов) целочисленных чисел. Для чего? Так как после сортировки данные в переданном слайсе будут отсортированы, мы будем передавать новый слайс неотсортированных данных для корректных результатов бенчмарка.

1. Наш бенчмарк выглядит так:

1. Исправим бенчмарк для BubbleSort:

1. Запустим наши бенчмарки:

1. Вспомним сложность алгоритмов из прошлых уроков:

BubbleSort при увеличении количества элементов потребляет все больше времени, тогда как алгоритм QuickSort тратит намного меньше с временной сложностью n log(n). В нашем случае сортировка ускорилась примерно в 3.5 раза!

Не забывай смотреть в cheatsheet, специально подготовленный для тебя:

В Go используется своя реализация QuickSort — с ней ты можешь ознакомиться по ссылке.

Рекомендуем также изучить дополнительные материалы по теме:

• quicksort.go (github);

• Quick Sort (LR pointers);

• 2.8.1 QuickSort Algorithm.