QuickSort is slower for low range data

Question

Recently, I have been comparing different types of sorting algorithms in python. I noticed that my quicksort is not processing input where the values ​​are repeated.

def compare_asc(a, b):
    return a <= b


def partition(a, p, r, compare):
    pivot = a[r]
    i = p-1
    for j in range(p, r):
        if compare(a[j], pivot):
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i+1], a[r] = a[r], a[i+1]
    return i + 1


def part_quick_sort(a, p, r, compare):
    if p < r:
        q = partition(a, p, r, compare)
        part_quick_sort(a, p, q-1, compare)
        part_quick_sort(a, q+1, r, compare)


def quick_sort(a, compare):
    part_quick_sort(a, 0, len(a)-1, compare)
    return a

Then i check it

import numpy as np
from timeit import default_timer as timer
import sys

test_list1 = np.random.randint(-10000, 10000, size=10000).tolist()
start = timer()
test_list1 = quick_sort(test_list1, compare_asc)
elapsed = timer() - start
print(elapsed)

test_list2 = np.random.randint(0, 2, size=10000).tolist()
start = timer()
test_list2 = quick_sort(test_list2, compare_asc)
elapsed = timer() - start
print(elapsed)

In this example, I get RecursionError: maximum recursion depth exceeded in comparison, so I added sys.setrecursionlimit(1000000)and after that I get this output:

0.030029324000224733
5.489867554000284

Can someone explain why he throws this recursion depth error only while sorting the second list? And why is there such a big time difference?

Answer 1

: , , , . , .

quicksort , . " ", - : "", "" "".

" ". ,

; , , , ...

CODE

, . , . :

• quicksort, . , , O(N*log(N)), ( , ) O(N**2) .
• ( ) .
• , : .

:

from random import randrange

def partition(a, lo, hi, pivot):
    i = L = lo
    R = hi
    # invariants:
    # a[lo:L]  < pivot
    # a[L:i]  == pivot
    # a[i:R]     unknown
    # a[R:hi]  > pivot
    while i < R:
        elt = a[i]
        if elt < pivot:
            a[L], a[i] = elt, a[L]
            L += 1
            i += 1
        elif elt > pivot:
            R -= 1
            a[R], a[i] = elt, a[R]
        else:
            i += 1
    return L, R

def qsort(a, lo=0, hi=None):
    if hi is None:
        hi = len(a)

    while True:   # sort a[lo:hi] in place
        if hi - lo <= 1:
            return

        # select pivot ar random; else it easy to construct
        # inputs that systematically require quadratic time
        L, R = partition(a, lo, hi, a[randrange(lo, hi)])

        # must recur on only the shorter chunk to guarantee
        # worst-case recursion depth is logarithmic in hi-lo
        if L - lo <= hi - R:
            qsort(a, lo, L)
            # loop to do qsort(a, R, hi)
            lo = R
        else:
            qsort(a, R, hi)
            # loop to do qsort(a, lo, L)
            hi = L