Week 10 - Complexity of HeapSort Algorithm (episode 2)

Before I continue on episodes of "Complexity of heap sort algorithm", I'd like to do a little review about topics which we mention in recently lecture. Finite state machine, finite state automata or any nouns of finite state, is the most related topic to us right now. It has been mentioned in all my second year computer science courses. I also want to make a note for DFSA which is very important in csc236. It has been quizzed today before I got right track on solving and devising that diagram.

Here we go!!! Continue on the episode:

Week 9 - Complexity of HeapSort Algorithm (episode 1)

As we talks about time complexity in lecture, we have mentioned Merge and binary search. In order to follow up "Complexity", I would like to do more on the other kinds of sort. Heap sort is the first sorting algorithm I have learned in csc108 from last year which may be more impressive to most of you and me.

So, basically, there are two step algorithm in Heap sort. The first step is to build up a heap out of an array. Then the second step is to begin with removing the smallest element from the heap then put it into an array.

Here is the function I write for the Heap sort. I'd like to solve this complexity precisely in next episode.


def Heapify(A, i, n):
    l = Left( i )
    r = Right( i )
    if l A[ i ]:
        largest = l
    else:
        largest = i
    if r A[ largest ]:
        largest = r
    if largest != i:
        A[ i ], A[ largest ] = A[ largest ], A[ i ]
        Heapify(A, largest, n)


def BuildHeap(A):
    n = len(A) - 1
    for i in range( n/2 ,0 ,-1 ):
        Heapify(A, i, n)


def HeapSort(A):
    BuildHeap(A)
    HeapSize = len(A) - 1
    for i in range( HeapSize, 1 , -1 ):
        A[ 1 ],A[ i ] = A[ i ],A[ 1 ]
        HeapSize = HeapSize-1
        Heapify( A,1,HeapSize )

week 8 - Summing up as Assignment 2 and Midterm 2

As I was reviewing for the second midterm for csc236, I was also recalling the whole schedule of this course. Assignments and midterms come up periodically which may be a kinda annoying in my view due to I have very heavy load for fall. However, my opinion makes a turn this time. Summarizing what I learn in a period enhances my point of views on specific topics and memory. Then I sum up my notes in a new way. 

Practice is the best way to keep knowledge being impressive on your mind. Therefore, I rewrite my notes in the way like: 

# Left                                                                                        # Right

Summary                                                                              Corresponding Problems

      of

   Notes

                                                        # Bottom

                                         Learn from problems and key points

                                                        Proof structure

It is a pretty busy week for me so I would like to share one of problem episodes next time and go further. It is an interesting problem but not easy.