Sorting and Efficiency

There are various methods of sorting lists and those different methods have to be considered when a programmer wishes to sort lists of different builds and lengths. A programmer has to consider those variations in order to implement the most efficient sorting method.

Insertion sort is a sorting algorithm that iterates through the entire length of the list, and after each iteration, takes the first element from the unsorted part of the list, say x, (at the beginning it will be the element at index 0) and puts it in its place in the sorted part of the list (e.g. when the element after x is bigger than x and the element before x is smaller than x in the sorted part (or x is at index 0 or -1)). Henceforth, after each iteration, the sorted part of the list becomes bigger by one element, and the unsorted part becomes smaller by one element; until the unsorted part does not exist anymore and the entire list is sorted. its worst case performance would occur when the list is ordered decreasingly, as at every iteration the first element in the unsorted part would be inserted as the first element of the sorted part (iterating over the entire length of the sorted part of the list). This would be done n times (n = length of list) and so therefore Insertion sort has a O(n^2) as there would be n iterations (to traverse the list and insert) n times. Insertion Sort's Best Case Performance would occur when the list is already ordered increasingly, as there would not be any displacement of elements (the sorted part would solely increase at every iteration) therefore BCP is O(n). This sorting algorithm is more efficient then others for a big list however, as there are not as many inversions as say, selection or bubble sort.

Selection sort is a different but similar sorting algorithm that takes the minimum value from the unsorted part of the list and puts it as the last element of the sorted part (equivalently to Insertion sort, the sorting part increases by one and unsorted decreases by one after each iteration of the function). Henceforth, the function has to iterate over all of the elements of the unsorted part at every iteration to 'make sure' that there is no other number smaller than the 'current minimum'. This algorithm is not the most efficient because as it happens, even when the list is sorted, the function iterates over all of the elements in a list, L, every time it adds an element to the sorted part of the list. Therefore its runtime is always the same, namely (n-1)n : runs over all elements in the list (n-1) times.

Bubble sort is another algorithm that in some cases is more efficient than selection and in other less. the algorithm consists of comparing pair of values in the unsorted part of the list (in this algorithm the sorted part is at the end of the list 'incrementing' downwards until the first element of the list is also sorted) and if the element at index i's value is smaller than element at index i+1's value, it will switch between the two, and i will be incremented by one, therefore the function compares the next two elements, until it reaches the end of the unsorted part of the list, whereby the largest element is added to the beginning of the sorted part of the list. Similarly to the other sorting algorithms this process is repeated until the sorted part of the list is equal to the list itself. Just like the previously mentioned algorithms, Bubble Sort's worst case performance will occur when the list is ordered decreasingly, as there will be at least n inversions, n times (n being the length of the list) so Bubble sort has a O(n^2). One of the main advantages of Bubble Sort however, is its capability of quickly recognizing whether a list is already ordered or not, as it compares all pairs of elements in the list.

Merge Sort is a rather efficient algorithm due to the fact that it applies the method of 'divide and conquer'. It splits the to-be-ordered list continually using recursion. If the lists that we end up with is empty or has only one item, they are ordered by definition. Otherwise new lists are recreated by comparing the first elements of two smaller lists at a time and merging them. This is done by recreating bigger, and bigger lists, until the final list is made, and there is no longer anything two lists that have to be compared as all of them have been merged into one, in order. this algorithm Worst case performance has O(nlogn) as it splits the list logn times (since the algorithm splits the a list of length 2, 1 time; a list of 4, two times (makes 2 lists of size 2 and comparing them within each other before merging them together. and for a list of size 8, it splits into two lists of 4... 2... etc..). after the splitting comes the merging, where the function has to put all the elements of the lists into the new list (i.e. n passes), as many times as the list was split. therefore the runtime is nlogn. it is faster on average then quicksort, as it makes less comparisons.

The Quick Sort algorithm also uses a divide and conquer method. it does so by partitioning the list using by firstly locating two position markers at the beginning and at the end of the remaining items in the list that is not sorted and picking a pivot value (it is usually random). It then moves the items that are on the wrong side of the value (if smaller to the right, if bigger to left) to the right side, while converging the right and left position markers towards the split point. Henceforth after each iteration, the left and right markers approach each other until they cross each other's path. This signifies that all the values in the list are ordered as all the values to the left of the left mark are ordered and all the values to the right of the right mark are also ordered. The worst case performance of this algorithm occurs when the pivot value is always the biggest one in the unsorted part of the list, which is rather rare. This however also has a O(nlogn) as it does the left and right side sorting n times (until left mark has crossed with right mark (i.e. times (right mark incrementing leftwards) + times (left mark incrementing rightwards) = size of list = n)).

The final sorting algorithm that was discussed in this course is Python's built in sort. It combines all the different aforementioned sorting algorithms and using each one of them when it is most efficient to do so (with respect to size, how ordered it is and a number of other combination of factors). It basically does the programmer's work by choosing the most efficient sorting algorithm. However, if one does not trust or does not wish to use a great algorithm that was created by a great man, Tim Peters: one can always use the sorting algorithms that are explained in this post.  

Recursion

Recursion

Throughout the last few weeks we have encompassed most of the introduction to recursion via multiple worked and traced example functions in class and during the tutorials.

Recursion allows programmers to write functions that run much faster. The problem that the programmer is trying to solve is broken down from its most complex version into sub-problems and so forth until the function arrives to a base case.

Henceforth, in order to write a recursive function, one has to identify what the base case is (e.g. in what case will the function be run at is simplest form) and place it in the code written under (or for) the 'else' statement. Furthermore, in order to write the function, the programmer has to identify how the values returned by the function for each value of the function's parameter are related. E.g. for a function f(x:int)-> int: what is the relationship between f(2) and f(3) and how do I find f(3) if I already have f(2). After that, the programmer needs to identify what will be the value that will change every time, the iterator that will get make the recursive function reach its base case after a while. For example:

in this case the iterator is i. it permits the function to run through all the possible elements in a nested list. The base case is when there are no more nested depths to the list currently being iterated over. When this case is reached the function simply finds the values that are equal to 3 and deletes them. If there is a list inside a list, the function will recursively enter all of them by calling itself until there are no more and the base case is reached.

Although recursion may seem complex at first for most programmers. Once one wraps his/her head around it, it makes the programmer's life much easier and allows him/her to write programs that are much more efficient and powerful.

  

Object-Oriented Programming

Lectures and Miscellaneous
    Object-Oriented programming is a section of computer science which contains extremely useful tools to organize, schedule and assess whatever the programmer/user wishes to work with.
Throughout this week I have learnt how one may derive and create his/her own parameters and rules for a type that they want to create.
    Furthermore, learning that programmers are able to create a Superclass from which they may create subclasses, opened up an entire new horizon and aspect of OOP that I did not know.  This allows me to only imagine how much can be done with OOP and how useful it can be for any organization when it wants to set up a database which will be able to count, and recount all the different elements that that organization contains.

    A technical aspect that I discovered this week was the fact that in a function defined with a class, if one wishes to call the function within its own body, there have to be default values for that same function in order for it to function.

Tutorial
    In order to remove the first element in a list until the list is empty, while maintaining a constant running time (not dependent on the size of the list) my partner and I discovered the function popleft(), and finished the lab within 1/3 of the time allocated for it. However, the T.A. asked us to review our function and try to do it a different way. Our solution allowed me to view lists from a different perspective: one where you don't have to change the actual list in order for a specific item to be acknowledged as the first one, you can do that solely by tweaking with the indices of the different elements inside the list.
    In the tutorial this week, I learned that even though it is always useful to be lazy (while still efficient and correct) while programming, sometimes in order to learn new skills or understand the material better, one may wish to go through a "little less lazy" way.