Sorting And Efficiency

I learned a bunch of vague concepts and abstract algorithms in middle school. That was a long dark time for any student who has no patience and self-regulation. For me, of course, algorithms are definitely not easy. However, among those tricky and  incomprehensible algorithms, sorting is the area that I spent most of my time on. I would like to share my interesting opinions about sorting algorithms here.

Sorting algorithms are useful. No one could deny that. Our computers are sorting things every single second. There are dozens of sorting algorithms scientists have analyzed and most of them have their own characteristics. These differentiate algorithms from each other. I would like to talk about the differences here.

First, i want to talk about time complexity,  the most important aspect in measuring a algorithm.

The Quick Sort,who has the fanciest name and the most mercurial time complexity, has a nlogn asymptotic complexity in best case, very decent and efficient. However, in the worst case, it seems not decent at all, a O(n^2) complexity. Quicksort is a divide and conquer algorithm which relies on a partition operation. The nlogn time complexity together with logn space usage make it one of the most popular sorting algorithms. The drawbacks of quick sort are quite obvious. Its worst-case performance is O(n^2).The most complex issue in quicksort is choosing a good pivot element , as consistently poor choices of pivots can directly result in drastically slower to a O(n^2) performance.

While there are probably a uncounted number of sorting algorithms, in practical implementations a few algorithms predominate. Like quicksort, each algorithm has its own advantages and drawbacks. Primarily heap sort, quicksort and merge sort are used for large data sets. While insertion sort is wildly used for small data sets because of its asymptotic inefficiency, decent space usage and stability. 

Recursion

Week4

Recursion is not a new thing but actually everyone who's never known it before really need a long time to get used to it. Most people like to read a recursive function by tracing it step by step, using a stack or something like that. Of course, it is the easiest way to do it. But we still got other ways. Because of the recursiveness, we can try to understand the basic part of a recursive function, and then repeat it over and over in our mind to get to the final result.

Object-oriented programming

we talked about object-oriented programming in the 2nd week of class

the basic definition of object-oriented programming is quite abstract and vague. I could not understand it clearly so I read a series of materials about the definition of “programming paradigm” and what it represents. I want to conclude it here by using simple and clear words.

The word “object” basically represents a concept that we (designers) use attributes and associated procedures to represent any thought, phenomenon, or in simple words, thing . The “objects” are usually instances of classes, also able to be used to interact with other applications or computer programs. They have some real meanings that are not abstract and easy for designers and users to apprehend, such as , points , cups or clients.

The first goal of OOP is, of course, to increase understanding.

There is a huge gap between users and developers in other programming paradigm, such as, functional or logic paradigm. Developers used to talking about database, subroutines or other unreadable structures all the time. Before the age of OOP, the programs were so impenetrable that most of readers(users) had to read a program by tracing it step by step. For example,the notorious “GO TO” instruction witnessed the darkest time of programming paradigm for both developers and users.  OPP has extremely lessened the the distance. Rather than focusing on logic or functions, OPP gave a brand new way to “program” our thoughts. We build objects that represent real stuff in our daily life. It essentially merges abstract data types with structured programming and divides systems into modular objects which own their own data and are responsible for their own behavior.