Sorting and Efficiency

Today I would like to introduce several sorting method by python language and compare their efficiency by Big O

First one: Insertion Sort

def insertion_sort(sort_list):

     iter_len = len(sort_list)

     if iter_len < 2:

         return sort_list 

    for i in range(1, iter_len):

         key = sort_list[i]

         j = i - 1 

        while j>=0 and sort_list[j]>key:

             sort_list[j+1] = sort_list[j]

             j -= 1 

        sort_list[j+1] = key

    return sort_list 

Insertion sort has two nested loops:

Outer loop runs once for each element in the original unsorted loop

Inner loop runs through sorted list to find the right insertion point

And thus the efficiency is O(n^2)

Second one: Selection Sort

def selection_sort(sort_list):

     iter_len = len(sort_list)

     if iter_len < 2: 

        return sort_list

     for i in range(iter_len-1):

         smallest = sort_list[i]

         location = i 

        for j in range(i, iter_len):

             if sort_list[j] < smallest:

                 smallest = sort_list[j]

                 location = j

         if i != location: 

            sort_list[i], sort_list[location] = sort_list[location], sort_list[i] 

    return sort_list

The basic idea of selection sort is: 

For each element i in the list:

1) „Find the smallest element j in the rest of the list

2) Swap i and j

And thus the efficiency is O(n^2/2)=O(n^2)

Third one: Bubble Sort

def bubble_sort(sort_list):

     iter_len = len(sort_list)

     if iter_len < 2:

         return sort_list

     for i in range(iter_len-1):

         for j in range(iter_len-i-1):

             if sort_list[j] > sort_list[j+1]: 

                sort_list[j], sort_list[j+1] = sort_list[j+1], sort_list[j] 

    return sort_list

The basic idea of bubble sort is:

Run through the array, exchanging values that are out of order

Outer loop can execute a maximum of n-1 times

Inner loop can execute a maximum of n-1 times

And thus the efficiency is O((n-1)^2) = O(n^2)

For now we can see that the three sorting algorithms introduced above all have the same efficiency O(n^2)

So do we have any more efficient algorithm?

And the answer is Yes!

Fourth one: Merge Sort

def merge_sort(sort_list):

    def merge2(L1:list, L2:list) -> list:

        L = []

        L1.reverse()

        L2.reverse()

        while L1 and L2:

            if L1[-1] < L2[-1]:

                L.append(L1.pop())

            else:

                L.append(L2.pop())

        L1.reverse()

        L2.reverse()

        return L + L1 + L2

    if len(sort_list) < 2 :

        return sort_list

    else :

        left_sublist = sort_list[:len(sort_list)//2]

        right_sublist = sort_list[len(sort_list)//2:]

        return merge(merge_sort(left_sublist), merge_sort(right_sublist))

The basic idea of Merge Sort is:

1）Break the data into two equal halves

2）Sort the halves

3）Merge the two sorted lists

And here we sort the halves by recursion

It's easy to find out that the efficiency of step Merge is O(n)

And it's also not difficult to conclude that the number we splits the list is O(logn)

And thus the efficiency of Merge Sort is O(nlogn) < O(n^2)

Recursion

1 . Introduction
Recursive algorithm is an algorithm calls itself indirectly or directly . In computer programming, a recursive algorithm to solve some of the problems is very effective .  It tends to make the description of the algorithm  simple and easy to understand . Hence, when it is difficult to solve the problem by using non-recursive method , try using a recursive method may give you unexpected surprise.

2 . Features 
Recursive programs during execution always call their own, and every time they calling itself,  the scale are usually narrowed. And when the scale of the problem is reduced a certain value, for which the program can directly give answers instead of recursively calling itself .Therefore each recursive call is conditional (the condition is often considered as the size of the scale), and there is close relationship between adjacent two calls (usually the output of the previous one serves as the input of the latter one). Additionally, what I think is the most important thing in recursive programming is that when using a recursive strategy, we must have a clear end , also known as recursive exports.

3.Application
In my opinion, recursive algorithm is generally used to solve three problems : 
1) The data is defined b recursion 
    example: Fibonacci function
2) The algorithm for solving a problem is a recursion
    example: Tower of Hanoi
3) structure of data is based on a recursive definition
    example: Binary tree

Object-oriented programming

This semester is my first time to get in touch with python. Compared with c++, I think that python is more programmer-friendly.

Since the theme of this paragraph is object-oriented programming , so I plan to talk about some of my peronal with combination of things that I learnt in the class.

First of all,  I would like to introduce the concept of "class".
Generally speaking, the class defines the properties of a things and its behavior.
For example, let's define a new class "dog" .This class will contain some properties about a dog, such as its name, breed and colour

class dog:
          def __init__(self:'dog', breed: str, name: str, colour: str ):
                self.breed=breed
                self.name=name
                self.colour=colour

Note that "__init__" contains the basic information( initial condition) about your class. And what you put in the "__init__" can be used in your following functions.


The second one is object. If we say that "class" is to define the abstract charactertistics of a thing, "object" is an insatnce of this thing. In other words, we can create things in the class we have just defined.For example:

Dog1=dog("Jack","dalmatian",“black and white”)

Then we have a dalmatian dog whose name is Jack and colour is black and white.

Next is about method. "Method",  which can be seen as ability, is used to define what a class can do but may not necessarily to do. For example, just like in the real world, a dog may bark, play, eat,sleep ,etc.
Then we can just define bark,play,eat and sleep as four method under the class dog.
Then after we create a new object , we can use these mathods.
Dog1.bark()
Dog1.play()
Dog1.eat()
Dog1.sleep()

I also met some difficulties when learning object-oriented programming. At first, I always confused class with function. I didn't understand the meaning of a class. I thought every class can be replaced by a combination of funtions!

But after I learned the python example of "stack", I figured out that though some of the classes can be replaced with function, class can make our programming easier, because in object-oriented programming each object sis able to accept data, process the data and communicate with other objects, so they can be seen as small "machines" .