Sorting algorithms selection sort, quick sort, merge sort (Week 12)

Since I wrote 6 sorting algorithms last week, I would write some more details about selection sort, quick sort, merge sort. For these three different sorting algorithms, they have different run times at different inputs.

When they have randomized input, merge sort and quick sort have the most efficiency which are O(nlogn). Selection sort worse than the other two, which is O(n^2). When they have Reverse-sort input, selection sort and merge sort do not change at all. Selection sort is O(n^2). Merge sort is O(nlogn). However, Quick sort changes a lot, becomes to the worst efficiency, which is O(n^2), When they have sorted input, Selection sort still is the worst, which is O(n^2). Quick sort is O(nlogn) and merge sort is O(n). Merge sort have the most efficiency.

In conclusion, Select  sort is the most stable soring algorithms at any situations. For the other sorts, we need to use them at specific input.

This is our last SLOG, thank you for reading my blogger!

Good luck for our final exam! Fighting!!!

Sorting big-Oh for lab 9(Week 11)

Nearly-sorted input

Reverse-sort input

                                                              Randomized input

During our lab9, we did some analyses on sorting. There were 6 sorting methods we discussed. Selection, Insertion, Bubble, Merge , Quicksort, list.sort. We found the average case for Bubble, Insertion and Selection are O(n^2), Merge and quicksort are O(nlogn), list.sort is O(n). In the end, we found list.sort is the most stable in six sorting methods. The 3 graphs above are their runtime trends. The 3 tables below are their runtime details.

Random	100	200	300	400	500	600
Selection	0.00175	0.00448	0.010012	0.01794	0.028137	0.043832
Insertion (1)	0.001457	0.005964	0.012746	0.022136	0.034737	0.0538
Bubble (1)	0.002344	0.009587	0.021157	0.036821	0.060712	0.090284
Merge (1)	0.000748	0.001684	0.00278	0.00365	0.004675	0.00582
Quicksort (1)	0.000528	0.001212	0.002021	0.002537	0.003176	0.004041
list.sort	0.000026	0.00006	0.000098	0.000138	0.000181	0.000222
Sorted	100	200	300	400	500	600
Selection	0.001451	0.004507	0.00984	0.017734	0.02751	0.039828
Insertion (1)	0.000092	0.000109	0.000302	0.000403	0.000491	0.000602
Bubble (1)	0.001308	0.005093	0.011387	0.020254	0.031784	0.046298
Merge (1)	0.000572	0.001217	0.001944	0.002637	0.003372	0.004105
Quicksort (1)	0.000911	0.002744	0.004596	0.006878	0.009558	0.012427
list.sort	0.000027	0.00006	0.0001	0.000139	0.000183	0.000227
Sorted, reversed	100	200	300	400	500	600
Selection	0.001882	0.004683	0.010407	0.018529	0.029347	0.041515
Insertion (1)	0.002878	0.011151	0.024815	0.044362	0.069045	0.10773
Bubble (1)	0.003478	0.013683	0.030688	0.054437	0.087364	0.129299
Merge (1)	0.00645	0.001399	0.002183	0.002965	0.003652	0.004605
Quicksort (1)	0.001841	0.006883	0.015072	0.026561	0.041432	0.059968
list.sort	0.000026	0.00062	0.0001	0.000141	0.000183	0.000224

 

Term Test 2 ( Week 10)

This week, we do not have any lectures due to Fall break and Term test2. So I just want to spend some time to conclude our Term test2. The questions were entirely based on binary trees and binary search trees. There were three questions in total. First question needed us to count interior nodes and the number of leaves. I just wrote two helper function, one was count_interior and the other was count_leaves, return (count_interior, count_leaves).

Second question needed us to return number of nodes with value that is an even int. I wrote such long codes. But professor only wrote in a line, which was return

(count_even(n.left) + count_even(n.right) + (1 if n.value % 2 == 0 else 0) if n else 0)

That’s amazing! The most excited was the third question. We needed to build a linked list of the path from root to minimum element and return the first node in the linked list. For example,

>>> min_path(BSTNode(4, BSTNode(3, None, None), BSTNode(5, None, None)))

LLNode(4, LLNode(3, None))

I had no idea. However, our professor gave us only a line as well.

return LLNode(n.value, min_path(n.left)) if n else None

That let me learn so much! I need more time to understand them.

Assignment 2 (Week 9)

The second term test is coming!

Last week, we just finished our Assignment 2. We were modeling Regular Expressions as trees. It is really funny and quite hard. Every regex can be represented as a tree. Each leaf node contains exactly one of ‘0’, ‘1’, or ‘e’. Each internal node contains exactly one of ‘.’(Dot), ‘|’(Bar), or ‘*’(Star).

Basic idea as follow:
Firstly, we needed to transform ‘0’,’1’,’e’ to a RegexTreeNode. For example, RegexTreeNode("0",[]),RegexTreeNode("1",[]),RegexTreeNode("e", [])

Then,we needed to think about ‘.’(Dot), ‘|’(Bar),‘*’(Star).
If Regular expression is '((1.(0|1)*).0)', we should get node like DotNode(DotNode(RegexTreeNode('1', []), StarNode(BarNode(RegexTreeNode('0', []),
RegexTreeNode('1', [])))), RegexTreeNode('0', []))

Secondly, we needed to matches RegexTreeNodes and strings.
For example, match(RegexTreeNode('1', []), '10')，should return False.
Because in RegexTreeNode only has ‘1’, not ‘0’.

We just did it recursively with some conditions.

Here is our code for regex_match function:

def regex_match(r, s):
    '''(RegexTree, str) -> bool
    Return True iff r matches s.
    '''
    # r with length 1
    if r.symbol == '0':
        return s == '0'
    if r.symbol == '1':
        return s == '1'
    if r.symbol == 'e':
        return s == ''
    # StarNode
    if isinstance(r, StarNode):
        if s == '':
            return True
        for i in range(len(s)):
            if s[i] == r.children[0].symbol and s[i] * len(s) == s:
                return regex_match(r.children[0], s[i])
            return False
    # BarNode
    if isinstance(r, BarNode):
        return any((regex_match(r.children[0], s),
                    regex_match(r.children[1], s)))
    # DotNode
    if isinstance(r, DotNode):
        if s == '':
            return (regex_match(r.children[0], s) and
                    regex_match(r.children[1], s))
        else:
            for i in range(len(s)):
                s1 = s[:i]
                s2 = s[i:]
            return (regex_match(r.children[0], s1) and
                    regex_match(r.children[1], s2))


In the end, good luck for our term test 2!

Binary search tree and Big O ( Week 8)

We learn Binary search tree this week. It is very important for us when we need do a large numbers of search. Like we know the run time is O(log n).

There are 4 basic conditions for Binary search tree:

1. The left subtree of a node contains only nodes with keys less than the node's key.

2. The right subtree of a node contains only nodes with keys greater than the node's key.

3. The left and right subtree each must also be a binary search tree.

4. There must be no duplicate nodes.

In our TUT, we also practiced to use Binary Search Tree. 

Here is our example:

We wrote _count_less function for helping count_less function.

    def count_less(self: 'BST', value: object) -> int:

        """

        Return the number of values in this BST that are strictly 
        less than value.

        """

        return BST._count_less(self.root, value)  # stub

    

    def _count_less(root: '_BSTNode', value: object) -> int:

        if root:

            if value > root.value:

                return  BST._count_less(root.left, value) + 1 \
                        + BST._count_less(root.right, value)

            else:   

                return BST._count_less(root.left, value)

        return 0