Sorting and Efficiency

Everyone knows that when you are looking for something, it's easier when the place where you're looking is neat. The same applies to computer science. When you are looking for a number in a large list of numbers, an easy way to do so is to first sort the list.
There are different methods of sorting in python:


1. BubbleSort
In BubbleSort, we compare adjacent pair of numbers by first taking the first and second numbers from the left. If the number on the left is greater than the one on the right, swap it. Then, take the second and third numbers, again comparing them and swapping if the number on the left is greater than the number of the right. Continue this process until the largest number is to the far right. This is know as the first pass. After the first pass, we are now working with n-1 items in the list. So we start the process with the second number in the list from the left. Continue each pass until the list is sorted.
Here is an example on a small list:
L = [1, 0, 4, 2, 3]

First pass:
Step 1 - 1 > 0, therefore swap. L = [0, 1, 4, 2, 3]
Step 2 - 1 < 4, therefore no change. L = [0, 1, 4, 3, 2]
Step 3 - 4 > 3, therefore swap. L = [0, 1, 3, 4, 2]
Step 4 - 4 > 2, therefore swap. L = [0, 1, 3, 2, 4]

Second pass:
Step 1 - 1 < 3, therefore no change.
Step 2 - 3 > 2, therefore swap. L = [0, 1, 2, 3, 4]
Step 3 - 3 < 4, therefore no change.

List is now sorted. This method is probably the most inefficient as it must exchange items until the last location is known.
Therefore the time complexity of the BubbleSort would be at most O(n^2)


2. SelectionSort
The SelectionSort is an improvement of the BubbleSort. Like it name indicates, it uses a selection method. During the first pass, it looks for the largest number and swap it with the n-item in the list.
During the second, it now looks for the second largest number and swap it with the n-1 item in the list.
Here is an example on a small list:
L = [43, 50, 47, 24, 12]

First pass:
50 is the largest, swap it with 12. L = [43, 12, 47, 24, 50]

Second pass:
47 is the largest, swap it with 24. L = [43, 12, 24, 47, 50]

Third pass:
43 is the largest, swap it with 24. L = [24, 12, 43, 47, 50]

Fourth pass:
24 is the largest, swap it with 12. L = [12, 24, 43, 47, 50]

List is now sorted. Since it makes pretty much the same number of comparisons as the BubbleSort, the time complexity of the SelectionSort is also, at most, O(n^2)


3. InsertionSort
This method is different from the previous two mentioned above. It works by always keeping a sorted sublist in the left side of the list. Whenever a number is larger than the one after it, it is inserted in the sorted sublist. If the number on the right is greater than the number on the left, it is only added to the right of the number on the left, in the sublist.
Here is an example on a small list:
L = [53, 26, 80, 70, 51]

First pass:
53 is the first number in the sorted sublist.
53 > 26, therefore insertion. L = [26, 53, 80, 70, 51]

Second pass:
53 and 26 are in the sorted sublist.
53 < 80, therefore 80 is only inserted in the sorted sublist, to the far right. L = [26, 53, 80, 70, 51]

Third pass:
53, 26 and 80 are in the sorted sublist.
70 < 80, therefore insertion. L = [26, 53, 70, 80, 51]

Fourth pass:
53, 26, 80 and 70 are in the sorted sublist.
51 < 80, therefore insertion. L = [26, 51, 53, 70, 80]

Note that the sublist is always sorted.  It begins with only the first number of the main list in it, and goes on until all the numbers from the main list are in the sublist.
Its time complexity is also O(n^2) at most.


4. ShellSort
The ShellSort is an improvement of the InsertionSort. It works by breaking the main list into smaller sublists, where each one of them are sorted using the InsertionSort method.
Here is an example.
Let L = [54, 26, 93, 17, 77, 31, 44, 55, 20]
We break L into three sublists:
L1 = [54, 17, 44]
L2 = [26, 77, 55]
L3 = [93, 31, 20]

Next, we sort each sublist.
L1_sorted = [17, 44, 54]
L2_sorted = [26, 77, 55]
L3_sorted = [20, 31, 93]

Once every sublists have been sorted, increment them together to form the main list, now sorted.
Being an improvement of the InsertionSort method, the time complexity of the ShellSort is at most between O(n) and O(n^2).


5. MergeSort
This method uses a divide and conquer strategy. Unlike the first four methods, the MergeSort is a recursive algorithm that continually divides a list in half. A list is then sorted if and only if it is empty or has only one item. We then use the operation called merging. Merging is the process of taking two smaller lists and combining them together to form a single, sorted list.
Here is an example:
Let L = [54, 26, 93, 17, 77, 31, 44, 55, 20]

Using the MergeSort, the list has been splitted into smaller lists.
We now use the merge operation to merge the smaller lists into one single list.

A MergeSort is a O(n log n) algorithm.

Week 9 - BST and TreeList

So this week's material was great. Learning more about Binary Search Tree has been really helpful. BST is really efficient as it allows us to ignore half of the list.
Perhaps the only challenging thing from this week was the exercise. Fortunately the use of recursion made it easier!

Recursion

Did you ever have to work on a code where you had to repeat the same lines over and over again? Where you had to work on a really big and complex problem?

Well, one way of dealing with those situations would be to use recursion. Recursion is the process of breaking down big, complex problems into smaller, simpler ones. These smaller problems are, in fact, repetitions of the bigger ones. Recursion is pretty similar to the divide and conquer technique. Instead of tackling a really perplex problem, we break it down into smaller instances of itself and work on those easier ones, then combine all the solutions obtained to get a better understanding of the bigger, complex problem.

Here's one example of recursion which we did in our 4th lab:

def bin_rep(n):
    """
    Produce the binary string representing non-negative integer n in binary.
   
    >>> bin_rep(0)
    '0'
    >>> bin_rep(1)
    '1'
    >>> bin_rep(5)
    '101'
    """  

    if n == 1:
        return '1'
    elif n == 0:
        return '0'
    else:
        return bin_rep(n // 2) + bin_rep(n % 2)


So here, when n is greater than 1, the method bin_rep will repeat itself until n has broken down to 1 or 0. Lets say n is 500. Recursion will automatically break n down until it has become 0 or 1, recording all the solutions along the way.

I think that without recursion, the life of computer programmers would be really difficult. Recursion helps a lot when working on complex codes. It facilitate our job and is also better looking than 100+ amount of lines for only one code.

Object-Oriented Programming

Object-Oriented Programming, as the name says, is a type of programming revolving around an object. The object is the data structure of the program itself. This type of programming enables the user to not only define the data type of the structure, but also the types of operations that can be applied
to the data structure. A connection between several objects can also be created; this is called inheritance. Thus, many objects can inherit characteristics from other objects.

The advantages of OOP are listed below:
1. Creation of modules that do not need to be changed when a new type of object is added. The programmer only need to create a new object that inherits the features of the existing objects.

2. Because of the modularity of the program, its software is easier to maintain. In case of issues, only
part of the system need to be updated instead of making large-scale changes.

3. More efficient since new objects can inherit characteristics from older ones.


Finally, here are some disadvantages:
1. Object-oriented programs usually involve more lines of code. More lines of code mean larger program size and more complex programs.

2. Because of the large number of lines of code, object-oriented programs are slow as more instructions have to be executed.