# 11 Efficiency and sort

This week, we learned efficiency and sort


A sorting algorithm is an algorithm for sorting a set of elements. Different algorithm may be better for sorting under different circumstances. For example, even the worst and average case running time of merge sort and bubble sort are the same(both are O(n^2)), their best case running time are different: the best case running time of merge sort is nlog(n), and bubble sort is n. This explain why the bubble sort is better than merge sort in practice for small set of data, but as size of input data increases, the performance of bubble sort suddenly drop down and the exact opposite behavior can be found with merge sort.
The graph below shown nlog(n) vs. n

n is the linear line, and nlog(n) is another.

Another example is to show how one sorting algorithm is better than another. We now compare quick sort and bubble sort.
Even though the worst case running time of bubble sort and quick sort are both n^2, their average case running time are different:
the average  running time of quick sort is nlog(n), and the average running time of bubble sort is n^2.


The graph below will illustrate the behavior of their running time:

Therefore, obviously that the quick sort is better than bubble sort.


Also, in our lab #10, we worked through different kinds of sorting algorithms and record the results on chart, and then plot the result on a graph. The aim of this lab is to investigate how various sorting algorithm works.

Here are some worst case running time of sorting some often used sorting algorithm, i think to be familiar with them will be help on our test:

quicksort:  O(n^2)
Merge sort: O(n logn)
Insertion sort: O(n^2)
Selection sort: O(n^2)
Bubble sort: O(n^2)

Since big-oh is an upper-bound, we have the hierarchy:

O(1) is a subset of O(lgn) is a subset of O(n) is a subset of O(n^2) is a subset of O(n^3) is a subset O(2^n) is a subset O(n^n).

week #7 Recursion

Recursion is the process of repeating something in terms of itself again and again. We can also use recursive idea in programming language to solve problem by calling functions themselves to solve a smaller problem.

Now we can look at an example of recursion. Let's say we have a nested number list, a list whose element is either numbers or nested number list. When we are looking for the multiplication of a nested number list: [1, 2, [3, 4], 5], we cannot just simply define a function of multiplication (let's say the function called prod), and write

prod[1, 2, [3, 4], 5]

There will be a TypeError since integer and list cannot be multiplied together directly, so we need to use recursion.

or

 

 

 



 

week #4

Week #3: Object-oriented programming

Object-oriented programming

         Object-oriented programming is another type of programming. Earlier, most of the programs we have learned is procedural programming. However, object-oriented programming is more useful, efficient, and easier to modify that procedural programming.