Why is Hoare's quicksort slower than bubblesort?

Question

Python

Sorting algorithm code:

import numpy as np


def selection_sort(a): 
    length = len(a)
    for i in range(length - 1):
        index = i
        for j in range(i+1, length):
            if a[j] < a[index]:
                index = j
        a[i], a[index] = a[index], a[i]


def insertion_sort(a): 
    for i in range(1, len(a)):
        j = i
        save = a[j]
        while j > 0 and a[j-1] > save:
            a[j] = a[j-1]
            j -= 1
        a[j] = save
        
        
def bubble_sort(a): 
    is_sorted = False
    j = len(a) - 1
    while not is_sorted:
        is_sorted = True
        for i in range(j):
            if a[i] > a[i+1]:
                a[i], a[i+1] = a[i+1], a[i]
                is_sorted = False
        j -= 1


def quick_sort(a):
    if not a:
        return a
    x = np.random.choice(a)
    left = [i for i in a if i < x]
    mid = [i for i in a if i == x]
    right = [i for i in a if i > x]
    return quick_sort(left) + mid + quick_sort(right)

a = list(np.random.randint(0, 10, 1000))
%timeit selection_sort(a)

a = list(np.random.randint(0, 10, 1000))
%timeit insertion_sort(a)

a = list(np.random.randint(0, 10, 1000))
%timeit bubble_sort(a)

a = list(np.random.randint(0, 10, 1000))
%timeit quick_sort(a)

Python 3.7.11 gives results like this:
28.3 ms ± 182 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) # selection_sort
135 µs ± 2.36 µs per loop (mean ± std. dev. of 7 runs , 10000 loops each) # insertion_sort
80.7 µs ± 302 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each) # bubble_sort
391 µs ± 4.93 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) # quick_sort

What's wrong with the implementation of the quick_sort algorithm?

Answer 1

First, quicksort is slower than any bubbles on small numbers. This is fine. It has better asymptotics - it is much faster on large numbers. But the constant is worse because of the complexity of the algorithm - that's why it loses to the bubble on small numbers. In all library implementations of quicksort (and any other logarithmic sort) there is a check that if there are few numbers, then start a bubble or sort by inserts.
Increase the size of the arrays to be sorted to 100,000, or a million, and the quicksort should be faster.
Secondly, your quicksort is very suboptimally written. Your bubble sorts the array itself in place, while the quicksort constantly creates new arrays via concatenation. Take a normal implementationand at 1000 elements, the quicksort will already become faster than the bubble.

Answer 2

It's not about implementation.
Quicksort is really "fast" in the case of partially ordered arrays (which in real problems can occur at least as often as completely unordered ones). Moreover, for a correct study, it is not enough to take a fixed number of elements, but it is necessary to perform comparisons with different N. In general, in the O ()-notation, this is not so much about the time of a specific execution, but about how the execution time of the algorithm changes (increases) in dependence on N. The
issue is discussed on the Internet in a huge number of articles. Well, for example:
https://habr.com/ru/post/274017/
https://works.doklad.ru/view/w4c2OLj2iMk.html