Try to search your question here, if you can't find : Ask Any Question Now ?

how is sorting faster then linear(low constant)?

HomeCategory: stackoverflowhow is sorting faster then linear(low constant)?
Avatarkundan asked 1 week ago

I’ve compared the performances of some built-in sort functions in python 3 verses some algorithms that I know their performances. and I saw some unexpected results. I would like u to clarify those issues.

I used the “perfplot” library to compare the complexity of the algorithms visualized.

import numpy as np
import perfplot

# algorithms:


def sort(x):
    np.sort(x)
    return 0


def sort_c(x):
    np.sort_complex(x)
    np.sort_complex(x)
    return 0


def builtin(x):
    sorted(x)
    return 0


def c_linear_inplace(x):
    for i in range(len(x) - 1):
        if x[i] > x[i + 1]:
            x[i] = x[i] + x[i + 1]
            x[i + 1] = x[i] - x[i + 1]
            x[i] = x[i] - x[i + 1]
    return 0


def c_linear_outplace(x):
    a = x.copy()
    for i in range(len(x) - 1):
        if x[i] > x[i + 1]:
            a[i] = x[i + 1]
            a[i + 1] = x[i]
    x = a.copy()
    return 0

def c_nlogn(x):
    logn = int(np.ceil(np.log2(len(x))))
    for i in range(len(x)-1):
        for j in range(logn):
            x[i] = 0
    return 0

#comprasion:
perfplot.show(
    setup=np.random.rand,  # function to generate input for kernel by n
    kernels=[
        sort,
        sort_c,
        builtin,
        c_linear_inplace,
        c_linear_outplace,
        c_nlogn,
    ],
    labels=["sort", "sort_c", "builtin", "check: linear inplace", "check: linear not in place", "check: nlogn"],
    n_range=[2 ** k for k in range(15)],  # list of sizes of inputs, i"setup" function will be called with those values
    xlabel="len(a)",
)

visual comparaion

I expect all sort functions to be close to the nlogn() function or at least less efficient than the linear ones, and I expect “c_linear_inplace” would be faster than “c_linear_outplace”. but all built-in sort functions were much faster than the linear functions and the “c_linear_outplace” function was slower than the “c_linear_inplace” function.

1 Answers
Best Answer
AvatarMatthias answered 1 week ago
Your Answer

10 + 5 =

Popular Tags

WP Facebook Auto Publish Powered By : XYZScripts.com