Algorithm measurement

Asymptotic analysis is used to measure the efficienty and accuracy of algrithms.It refers to computing the running time of any operation in mathmatical units of computation.

Algrithm types:

Best case: Minimum time required for execution
Average case: Average time required for execution
Wrost case: Maxinum time required for execution

Asymptotic notations:

• O notation(Big Oh Notation): express the upper bound of an algrithm's running time. It measures the worse case time complexity or the longest amount of time an algrithm can possibly take to complete.

O(f(n)) =
{
g(n): there exists c > 0 and n0 such that f(n) <= c.g(n) for all n > n0
}

• Ω notation(Omega Notation): express the lower bound of an algrithm's running time. It measure the best case time complexity or the best amount of time an algrithm can possibly take to complete.

Ω(f(n)) >=
{
g(n): there exists c > 0 and n0 such that g(n) <= c.f(n) for all n > n0
}

• θ notation(Theta Notation): express both of lower bound and the upper bound of an algrithm's running time.

θ(f(n)) =
{
g(n) if and only if g(n)=O(f(n)) and g(n) = Ω(f(n)) for all n>n0
}

Common asymptotic notation

constant - O(1)
logarithmic - O(log n)
linear - O(n)
nlogn - O(n log n)
quadratic - O(n^2)
cubic - O(n^3)
polynomial - n^O(1)
exponential - 2^O(n)

Sorting algrithms

There are many different sorting algrithms in computer science. The major goal of these algrithms is to arrange the data from the list in orders. Different sorting algrithm has different performance, its effeciency depends on the case.

Bubble sorting

Time complexity:

Best: O(n)
Worse: O(n2)
Average: O(n2)
Stable: Yes
Method: Exchange

Selection sorting

Time complexity:

Best: O(n2)
Worse: O(n2)
Average: O(n2)
Stable: No
Method: Selection

Insert sorting

Time complexity:

Best: O(n)
Worse: O(n2)
Average: O(n2)
Stable: Yes
Method: Insertion

Shell sorting

Time complexity:

Best: O(n logn)
Worse: Depends on the gap sequence: best known is n4/3
Average: Depends on the gap sequence
Stable: No
Method: Insertion

Quick sorting

Time complexity:

Best: O(n logn)
Worse: O(n logn)
Average: O(n2)
Stable: typical in-place sort is not stable
Method: Partitioning

Merge sorting

Time complexity:

Best: O(n logn)
Worse: O(n logn)
Average: O(n logn)
Stable: Yes
Method: Merging

Radix sorting

Time complexity:

Best: -
Worse: O(n * k / d)
Average: O(n * k / d)
Stable: Yes

Bucket sorting

Time complexity:

Best: -
Worse: O(n * k / d)
Average: O(n * k / d)
Stable: Yes

Heap sorting

It's a comparision based sorting algrithm.
It's like a improved selection sort: it divided input data into a sorted and unsorted region, and it iteractively shrinks the unsorted region by extracting the largest element and moving it to the sorted region. It uses a heap data structure as the improvement rather than a linear-time search to find the maximum.

Time complexity:

Best: O(n logn)
Worse: O(n logn)
Average: O(n logn)
Stable: No
Method: Selection

Algorithm overview

it can be divided into 2 part:

1. Build a Max heap with the given input list.
2. Swap the first element of the list with final element, decrease the considered range of the list by one
3. Rebuild the heap as a max heap

Testing

SAMPLE_RANGE = 1000000
SAMPLE_LENGTH = 50000

sample_data = random.sample(range(SAMPLE_RANGE), SAMPLE_LENGTH)

Computer configuration:

cat /proc/cpuinfo  | grep 'model name' | uniq
model name	: Intel(R) Core(TM) i7-5500U CPU @ 2.40GHz
cat /proc/cpuinfo | grep 'processor' | wc -l
4

Result:

→ python sortings.py 
[bubble_sort_forward]   exe time:193.38096499443054
[bubble_sort_backward]  exe time:145.54550194740295
[select_sort]           exe time:180.65961289405823
[insert_sort]           exe time:177.1302089691162
[shell_sort]            exe time:174.22427916526794
[quick_sort]            exe_time:0.1404728889465332
[quick_sort1]           exe_time:0.1601569652557373
[merge_sort]            exe_time:0.21835017204284668
[radix_sort]            exe time:0.11922287940979004

Checking the relevant code from Github