• This is introduction about the algorithms coded in python. Python is a programming language with objects, modules, threads, exceptions and automatic memory management. The benefits of pythons are that that is simple and easy, portable, extensible, build-in data structure and it is an open source.

Python Common Algorithms

  • Definition of Algorithms
  • Time Complexity
  • Common algorithm examples

Definition of Algorithms

Algorithm is an accurate and complete description of the solution. It is a series of clear instructions for solving problems. The algorithm represents a systematic way to describe the problem-solving strategy. That is to say, it is possible to obtain the required output in a limited time for a certain specification input. If an algorithm is flawed or not suitable for a problem, executing this algorithm will not solve the problem. Different algorithms may accomplish the same task with different time, space or efficiency. The pros and cons of an algorithm can be measured in terms of space complexity and time complexity.

An algorithm should have the following seven important characteristics:
1) Finiteness: The finiteness of the algorithm means that the algorithm must be able to terminate after performing a limited number of steps;
2) Definiteness: Each step of the algorithm must have an exact definition;
3) Input: An algorithm has zero or more inputs to characterize the initial state of the operand. The so-called zero input means that the algorithm itself determines the initial condition;
4) Output: An algorithm has one or more outputs to reflect the results of processing the input data. Algorithms without output are meaningless;
5) Effectiveness: Any calculation step performed in the algorithm can be broken down into basic executable steps, that is, each calculation step can be completed in a limited time (also called validity);
6) High Efficiency: Fast execution and low resource consumption;
7) Robustness: Responding correctly to the data.

Time Complexity

In computer science, the time complexity of an algorithm is a function that quantitatively describes the running time of the algorithm. The time complexity is usually a Big-O notation. Big O notation is a mathematical symbol used to describe the progression of a function. Rather, it uses another (usually simpler) function to describe the asymptotic upper bound of the order of magnitude of a function. In mathematics, it is generally used to characterize the remainder of a truncated infinite series, especially an asymptotic series; in computer science, it is very useful in analyzing the complexity of an algorithm. The expression, when used in this way, the time complexity can be said to be asymptotic, which examines the case when the input value approaches infinity.

Common Algorithms Examples

Name Complexity Explanation
Bubble Sort O(N*N) Small number float upward
Insertion Sort O(N*N) Take out elements one by one
Selection Sort O(N*N) Recursion
Quick Sort O(N*log2(N)) Choose medium element
Heap Sort O(N*log2(N)) Approximate complete binary tree
Shell Sort O(n^(1+￡)) Choose a step
Bin Sort O(N) A sort of distribution sort

1) Bubble sort

1
2
3
4
5
6
7
8
9
10
11
12
data_set = [ 9,1,22,31,45,3,6,2,11 ]
loop_count = 0
for j in range(len(data_set)):
    for i in range(len(data_set) - j- 1): 
        if data_set[i] > data_set[i+1]: #switch
            tmp = data_set[i]
            data_set[i] = data_set[i+1]
            data_set[i+1] = tmp
        loop_count +=1
    print(data_set)
print(data_set)
print("loop times", loop_count)'

2) Selection sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
data_set = [ 9,1,22,31,45,3,6,2,11 ]
smallest_num_index = 0 #initialize the minimum, default is the first element.
 
loop_count = 0
for j in range(len(data_set)):
    for i in range(j,len(data_set)):
        if data_set[i] < data_set[smallest_num_index]: #current element less than min
            smallest_num_index = i
        loop_count +=1
    else:
        print("smallest num is ",data_set[smallest_num_index])
        tmp = data_set[smallest_num_index]
        data_set[smallest_num_index] =  data_set[j]
        data_set[j] = tmp
 
    print(data_set)
    print("loop times", loop_count)

3) Insertion sort

1
2
3
4
5
6
7
8
9
10
source = [92, 77, 67, 8, 6, 84, 55, 85, 43, 67]
for index in range(1,len(source)):
    current_val = source[index] 
    position = index
  
    while position > 0 and source[position-1] > current_val: 
        source[position] = source[position-1] 
        position -= 1 
    source[position] = current_val 
    print(source)