SLOG-WEEK Eleven Sorting and Efficiency

In programming, sorting is a method, which takes an unsorted list, and rearranges the elements in the unsorted list to a sorted list, in which has the elements in increasing or decreasing order. Furthermore, There are various ways to sort a list, and these ways are referred to some sorting algorithms. Example of sorting algorithms are: bubble sort, selection sort, insertion sort, merge sort, and quick sort (thanks to http://art5594.blogspot.ca after reading this slog, I have a better and clear understanding about sorting algorithms). All these sorting algorithms have different runtimes, which are the length an algorithm takes to complete a sorting task. Runtimes are generally depend on the size of a list, and we call this size 'n'.

Let's look at each type of sorting algorithm and see what their runtime will be under specific circumstances.


Bubble Sort

In bubble sort, the program compares adjacent pair of numbers by taking the first and second numbers from the left. If the number on the left is greater than the number on the right, then the program will swap them. after that, the program will compare the second and third numbers with the same algorithm, and this process is stopped when the largest number is to the far right. After that, the program now has to work with list of size n-1 since the largest number is to the far right. Thus the program start this process once again until the list is sorted.

Best case
The best case for bubble sort is when input a list that is already sorted, then it will not swap any number of the list because the list is sorted. The sorting algorithm just need to compare each adjacent number, and this takes O(n). Thus, the total runtime for best case bubble sort is O(n).

Average case
The average case for bubble sort involves the operation for comparing and the operation for swapping.
So comparing each number in the list takes O(n) and swapping numbers takes O(n). Therefore the total runtime for this case is O(n^2).

Worst case
The worst case for bubble sort is much the same as the average case. So total runtime would be O(n^2)




Selection sort

Selection sort is a sorting algorithm that goes through the entire list, finds the smallest number in the list and swaps it to the front of the list.

Cases
All cases for selection sort is O(n^2) because this algorithm goes through the entire list, swaps the smallest number to the front of the list, and then repeat for n-1 list. The formula is n(n-1) which is O(n^2).




Insertion sort

Insertion Sort is a sorting algorithm that first takes the first two indexes say, 0 and 1, and compares the number at index 0 and 1, and swap the number at index 0 and 1 into an increasing order. After that, index 0 and 1 is considered a sorted region. the sorting algorithm will then move forward one at a time and compares the number at that index is with the numbers in the sorted region, then the sorting algorithm will insert the number at that index in the right sorted region, and repeat this process until the number at last index is checked.

Best case

If the list is already sorted, then it will not have to swap them at all. In this case, the sorting algorithm has linear runtime of O(n). 

Average case

The sorting algorithm has to compare with part of the list, and find the right spot to insert the number. In this case it has a runtime of O(n^2)

Worst case

the worst case scenario is to input a sorted reverse order list. In this situation, it will have to compare with each number and insert  into the front of the list, and it will have to do it for each number. In this case it has a runtime of O(n^2)

Merge sort

Merge sort is a sorting algorithm that divide the unsorted list into n sublists, and each of the sublists contains 1 number. Furthermore, a list of 1 number is considered a sorted list. After that, the sorting algorithm will repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist left. Thus the only one sublist will be the sorted list.

Cases

The best, average, and worst case for Merge sort is O(nlog(n)) because it divides the unsorted list into n sublists which takes O(log(n)) and then merges sublists to produce new sorted sublists which takes O(n)

So together, the runtime for Merge sort is O(nlog(n)).

Quick sort

Quick sorts a sorting algorithm that first pick an number from the list, call this number a pivot. Then reorder the list so that all the numbers that are less than the pivot goes to the left of the pivot, and all the numbers that greater than the pivot goes to the right of  the pivot. After that, the pivot is in its final position. Then, recursively apply the above steps to the sublist of numbers with smaller numbers and separately to the sublist of numbers with greater numbers.

Best case

The runtime of best case for quick sort is O(nlog(n)), the operation that divides list into half lists takes O(log(n)), and the operation that swap left and right numbers takesO(n). So together, the total runtime is 

O(nlog(n)).

Average case

The runtime of a average case is same as a best case.

Worst case

If one chooses a very bad pivot which would be the largest number or the smallest number in the list. By doing that, the sorting algorithm will put all the numbers to one side, and this process will repeated n times. In this case, the runtime for quick sort is O(n^2).

Conclusion

To sum up, analyzing different type of sorting algorithms gives me a better understanding on their runtime and convinced me that certain sorting algorithms has certain best case and worst case performance.

Sources: http://commons.wikimedia.org/wiki/File:Quicksort-example.gif
              http://en.wikipedia.org/wiki/File:Bubble-sort-example-300px.gif
              http://en.wikipedia.org/wiki/File:Insertion-sort-example-300px.gif
              http://en.wikipedia.org/wiki/File:Selection-Sort-Animation.gif
              http://en.wikipedia.org/wiki/File:Merge-sort-example-300px.gif

SLOG-WEEK Ten

Prof Heap covered some concepts about analyzing algorithm in this week's lecture. In computer science  algorithm analysis is a field which deals with the efficiency of algorithms. Efficiency is determined by an algorithm's time complexity and memory usage instead of computer hardware(CPUs, GPUs etc). An algorithm's time complexity is determined by the input size and number of steps the function takes to complete its task. A notation to represent time complexity is the symbol of Big-Oh. For example, a linear algorithm has time complexity of O(n) because if the input size increases, the number of steps it takes to complete also increases, and vice versa. Furthermore, an algorithm has a time complexity of O(n^2) is when number of steps increases quadratically as the input increases.

 

Below is some time complexity classes in descending efficiency order.

O(1), O(log(n)), O(n), O(nlog(n)), O(n^2), O(2^n),O(n!)

There exist some algorithms that have same time complexity(O(1)) for every input, an example for that is the pop method (list) in python. However, most algorithms will be more efficient for some particular input while others will be less efficient. The time complexity also has three categories which are the best case, average case and worst case. Best case is when the algorithm is at its best performance, average case is when the algorithm is at its averages performance, and worst case is when the algorithm is at its worst case complexity. With theses three cases, we can perform analysis of the time complexities of algorithms. 

SLOG-Week Eight

In this week's lecture we continued to explore about LinkedList from last week. The concept of LinkedList initially has given me quite a hard time to understand. After I spend an hour on reading the class LinkedList after Monday’s lecture, now I understand the structure of a LinkedList. So, What is a LinkedList? It is very similar to a nested list. For example, a LinkedList should have this kind of structure LinkedList(0,LinkedList(1,LinkedList( ))), and think each LinkedList to be a node: a node is where some cargo or value is stored. By looking at this example, it is clear that a LinkedList is constructed with a series of linked nodes. Furthermore, in the example, the leftmost LinkedList(0, contains some value 0, we refer this portion to be the head, and LinkedList(1,LinkedList( ))) refers to the rest.

A picture to illustrate a LinkedList.

The methods of a LinkedList involves the operation of adding value which means more LinkedList nodes, and this method method is called “prepend.” another mothod is called “decapitate” witch deletes the head (the leftmost LinkedList) and make the leftmost of a rest to become a head. Few other methods are: insert(insert a LinkedList node into an existed LinkedList, delete(delete a LinkedList node from an existed LinkedList) and reverse(reverse a existed LinkedList).

This week we also learned about binary search, which is a searching algorithm. To put it simple, this type of search starts at the middle node of the LinkedList, and creates an upper-set (goes towards the end) and a lower-set (goes towards the front) of nodes. during the search, each LinkedList node is checked above and below until the value is found.

Thank you for reading my blog.

SLOG-Week Seven Recursion

Recursion is one of the most important topics in CSC148. When Prof Heap first introduced that topic back in week 4, I was amazed and at the same time, I was confused as well. What is recursion? In plain English recursion means “define something in terms of itself;” furthermore, in Programing language recursion means that a function can call itself to solve smaller sub problems. By looking at the definition, it seems pretty easy to understand. However, the concept of recursion was abstract for me when I first encountered it. I took the stubborn approach, which is tried to trace down every single step of a recursion code, and I thought that was the only way to understand it. This is where the confused part came in, after few traces I already felt it is impossible to trace anymore. I knew I was wrong, so I decided spend some time to fix my understanding about recursion. The result was good. First I think of an easiest example that does not require a recursive step. Second I modify the example so that it requires one recursive step. To phrase it better, I basically think of a base case and then modify it to become a recursive case, and that is it. No more headaches!

An example to look at is the freeze function which is from the lab I did in week 5, and this function takes an object and returns it. However, if I input a list as a parameter. It will return a copy of the list. so if I modify the old list, the new list will not be modified. 

def freeze(X: object) -> object:

    """

    >>> freeze('zxcds')

    'zxcds'

    >>> L1 = [1, [2, 3], 4]

    >>> L2 = freeze(L1)

    >>> L1 is L2

    False

    >>> L1 == L2

    True

    >>> L1[1] == L2[1]

    True

    """

    if isinstance(X, list):

        return [freeze(i) if isinstance(i, list) else i for i in X]

    else:

        return X

I first think of an non-recursive example say, [1, 2, 3,4].  I use list comprehension to make a copy of the old list. 

Then I write the non-recursive part of the code which is "else i for i in X]"

Then I modify the non-recursive example to a recursive one which only includes one recursive step say, [1, [2, 3], 4]. 

Then I write the recursive part of the code which is " [freeze(i) if isinstance(i, list)."

at index 1 which is a list of [2,3] and is where the recursion begins. "freeze(i)" is called and new list [2, 3] is produced, and a copy of [1, [2, 3], 4] is made.

Recursion is useful once I know how to write it.  One base case and one recursive case are crucial for writhing a recursive code.